Algo Part1

快速排序 #

q[l] — q[(l+r)/2] — q[r]

  • 分治算法, the divide and conquer class of algorithm
  1. 确定分界点 x, q[l] q[(l+r)/2] q[r] q[random]
  2. 根据 x 调整元素, 使得 <=x, x, >=x
  3. 递归处理, 得到 left, x, right

implement 1 #

  1. a[], b[]
  2. for q[l - r] if q[i] <= x, x->a[] if q[i] >= x, x->b[]
  3. a[]->q[], b[]->q[]

implement 2 two pointers #

  1. pointers，p1, p2, 从序列两端相向而行
  2. p1 <= x, p1 移动到下一个，否则 判断 p2
  3. p2 >= x, p2 移动到下一个，否则 交换 p1 p2
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int arr[N];

void quick_sort(int arr[], int low, int high)
{
  if (low >= high) return;

  int pivot = arr[low], left = low - 1; right = high + 1;
  while (left < right) {
      do left++; while (arr[left] < pivot);
      do right--; while (arr[right] > pivot);
      if (left < right) swap(arr[left], arr[right]);
  }

  quick_sort(arr, low, high);
  quick_sort(arr, right + 1, high);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++) printf("%d ", q[i]);

    int arr[] = { 24, 8, 42, 75, 29, 77, 38, 57 };
    // Sorted array: 8 24 29 38 42 57 75 77

    return 0;
}