排序算法

归并排序

• 时间复杂度 $O(n*long_2(n))$
• 空间复杂度 $O(n)$
• 稳定

// 使数组 arr 在 L,R 范围内有序
void process(vector<int>& arr, int L, int R) {
    if (L == R) return;
    int mid = L + ((R - L) >> 1);
    // 使 L,mid 区间有序
    process(arr, L, mid);
    // 使 mid,R 有序
    process(arr, mid + 1, R);
    // 经过上面两次过程，整体还是无序的，因此需要进行 merge
    mergeSort(arr, L, mid, R);
}

void mergeSort(vector<int>& arr, int L, int M, int R) {
    vector<int> help(R - L + 1);  // L,R 范围的辅助空间
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
        // p1 p2 都没越界，谁小就拷贝到 help
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.size(); ++i) {
        arr[L + i] = help[i];
    }
}

快速排序

• 时间复杂度 $O(n*long_2(n))$
• 空间复杂度 $O(long_2(n))$
• 不稳定

#include <random>

void quickSort(vector<int>& arr, int L, int R) {
    uniform_real_distribution<float> u(0, 1);
    default_random_engine e;
    if (L < R) {
        swap(arr[L + (int)(u(e) * (R - L + 1))], arr[R]);  // 随机选一个位置与最后一个数做交换
        vector<int> p = partition(arr, L, R);  // 长度为 2 的数组，p[0] p[1] 分别表示等于区域的左右边界
        quickSort(arr, L, p[0] - 1);  // 小于区域
        quickSort(arr, p[1] + 1, R);  // 大于区域
    }
}

vector<int> partition(vector<int>& arr, int L, int R) {
    int less = L - 1;  // 小于区域右边界
    int more = R;  // 大于区域左边界
    while (L < more) {  // L 表示当前数的位置，R 表示划分值的位置
        if (arr[L] < arr[R]) {
            swap(arr[++less], arr[L++]);
        }
        else if (arr[L] > arr[R]) {
            swap(arr[--more], arr[L]);
        }
        else {
            L++;
        }
    }
    swap(arr[more], arr[R]);
    return { less + 1, more };
}