两种排序：

1. 快速排序
2. 归并排序

以后以$q$代替一个无序数组

快速排序：

快排是基于分治的一种排序。

思想：

第一步：确定分界点$x$。$x$可以取

1. $q_l$，即最左边
2. $q_{(l+r)/2}$，即中间
3. $q_r$，即最右边
4. 随机值

第二步：调整区间（最难），使得$q$被$x$分成两半，左边小于等于$x$，右边大于等于$x$。有很多方法，最后再说。

第三步：递归处理左右两段。因为

1. $q$只剩两个值时，交换两数，便成了一个有序序列
2. 左右两边都排好后整个序列也排好了（左边最大值小于右边最小值）

第二步的处理方式：

简单的（暴力做法）：

1. 准备$a$，$b$两个数组。
2. 遍历一遍，把小于等于$x$的放进$a$数组，把大于的放进$b$数组。
3. 把$a$，$b$数组分别在放回原数组。

多定义了两个数组，时间复杂度也没降低，虽然想着简单也最好别用（况且代码打着也不怎么简单）。

y总优美而简洁方法：

1. 准备$i$，$j$两个指针，一个指头，一个指尾。
2. $i$一直往后走，直到$i$指的那个数大于$x$；$j$往前走，直到指的数小于$x$。
3. 如果$i$小于$j$就交换两个数
4. 一直重复$2$和$3$，直到$i$、$j$相遇或错开

不用开辟额外空间，打着也不难，非常nb.

模版：

void quick_sort(int q[], int l, int r){
    if (l >= r) return ;
    int x = q[l + r + 1 >> 1], i = l - 1, j = r + 1; // 第一步和定义第二步的两个指针
    while (i < j){
        do i++; while (i < j && q[i] < x);
        do j--; while (i < j && x < q[j]);
        if (i < j) swap(q[i], q[j]);
    } // 第二步
    quick_sort(q, l, i - 1), quick_sort(q, i, r); // 第三步
}

归并排序：

归并也是基于分治的一种排序。

思想：

第一步：确定分界点$mid$，$mid=(l+r)/2$。

第二步：用$mid$递归分开左右两边，只剩一个数时，自然就是有序的。

第三步：二路归并（最难），把两个有序序列合并成一个有序序列。方法是

1. 准备一个新的数组$res$记录答案，再准备数组$i$、$j$两个指针，分别指向两个序列的开头。
2. 对比$i$、$j$的值，哪个小，就把哪个放进$res$数组里，重复此操作。
3. 看两个数组哪个有剩余，把剩余的值都放进$res$数组里。
4. 把$res$数组的值挨个传给原数组。
   用到了双指针的思路。

模版：

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]) res[k++] = q[i++];
        else res[k++] = q[j++];
    }
    while (i <= mid) res[k++] = q[i++];
    while (j <= r) res[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++) q[i] = res[j];
}

------------------------------end------------------------------