[算法] 排序

• 插入排序

void insertSort(vector<uint>& A) {
    for (int j = 1; j < A.size(); j++) {
        uint x = A[j];
        int i = j - 1;
        while (i >= 0 && A[i] > x) {
            A[i+1] = A[i];
            i--;
        }
        A[i+1] = x;
    }
}

• 希尔排序
  缩小增量排序：先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序，然后取 d2(d2 < d1)重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1，最坏时间复杂度O(n^2)，优化Gap值可使得时间复杂度
  不稳定！

void shellSort(vector<uint>& A) {
    int n = (int)A.size();
    for (int gap = n/2; gap > 0; gap /= 2)
    {
        for (int j = gap; j < n; j++) {
            uint x = A[j];
            int i = j - gap;
            while (i >= 0 && A[i] > x) {
                A[i + gap] = A[i];
                  i -= gap;
            }
            A[i + gap] = x;
        }
    }

}

• 归并排序

void merge(vector<uint>& A, int p, int q, int r) {
    vector<uint> L;
    L.reserve(q-p+1);
    vector<uint> R;
    R.reserve(r-q);
    for (int i = p; i <= q; i++) {
        L.push_back(A[i]);
    }
    for (int i = q+1; i <= r; i++) {
        R.push_back(A[i]);
    }
    int i = 0, j = 0, k = p;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) {
            A[k++] = L[i++];
        } else {
            A[k++] = R[j++];
        }
    }
    while (i < L.size()) {
        A[k++] = L[i++];
    }
    while (j < R.size()) {
        A[k++] = R[j++];
    }
}

void mergeSort(vector<uint>& A, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q+1, r);
        merge(A, p, q, r);
    }
}

• 堆排序
  堆
  max-heapify(A, i)
  通过与I的左右子节点比较让A[I]的值逐级下降 O(lgn)
  build-heap(A)
  for I=A.length/2 to 1
  max-heapify(A, i)
  利用n/2+1...n均为叶子节点的特点将时间复杂度降为 O(n)
  Heapsort(A)
  首尾交换
  断尾重构
  不稳定！
• 快速排序
  虽然实际复杂度相等，但快速排序仍然比较快，因为堆排序是缓存不友好的，而相较于归并排序，快速排序是就地排序，没有归并额外的分配和销毁数组的开销
  不稳定！
• 计数排序

void countSort(vector<uint>& A, uint place) {
    int n = (int)A.size();
    vector<uint> output(n, 0);
    vector<uint> count(10, 0);
    for (int i = 0; i < n; i++) {
        count[(A[i] / place) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i-1];
    }
    for (int i = n-1; i >= 0; i--) {
        output[count[(A[i] / place) % 10] - 1] = A[i];
        count[(A[i] / place) % 10]--;
    }
    for (int i = 0; i < n; i++) {
        A[i] = output[i];
    }
}

稳定 O(n+k)

• 基数排序

void radixSort(vector<uint>& A, uint max) {
    
    uint place = 1u;
    int d = 1;
    uint p = 10u;
    while (max >= p)
    {
        max /= 10u;
        ++d;
    }
    for (int i = 0; i < d; i++) {
        countSort(A, place);
        place *= 10;
    }
}