01排序

快速排序

问题

将序列 q 的 l ~ r 区间排序
void quick_sort(int q[], int l, int r)

基本思想 —— 分治

1. 找一个参考值 x
2. 通过双指针算法交换使得 左半边全部是 <= x , 右半边全部是 >= x
   1. 移动左指针 i ，找到大于 x 的数
   2. 移动右指针 j ，找到小于 x 的数
   3. 交换逆序对
3. 递归处理 左半边 右半边

模板

void quick_sort(int q[], int l, int r){
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[l] + q[r] >> 1;
    while(i < j){
        while(q[++ i] < x);
        while(q[-- j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort( q, l, j), quick_sort( q, j + 1, r);
}

注意点： 分界点的选择可以是[ l , j ]、 [ j + 1 , r ] 或者 [ l, i - 1 ]、[ i , r ],
swap 的时候不要忘记判断 i < j

归并排序

与快排的先排完上层，再排下层不同，归并排序是先排完下层再排上层

问题

将序列 q 的 l ~ r 区间排序
void merge_sort(int q[], int l, int r)

基本思想

1. 先排完左半边[ l , mid ]、再排完右半边[ mid + 1, r ]
2. 将左右两个有序序列进行合并
   1. i , j 两个指针分别指向两个有序子序列的头，哪个小就输出哪个，并指向后一个，直到有一个序列指针到达末尾
   2. 将未全部输出的序列全部输出
3. 处理左半边 和 右半边 同样使用递归的方式

模板

int tmp[N]; // 很大，最好开在外面
void merge_sort(int q[], int l, int r){
    if(l >= r) return; // 递归的出口
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];

    for(int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}