笔记的内容来源于算法基础课

排序

对于给定的数组q，在[l, r]之间进行从小到大的排序

快速排序

基于分治的思想，将整个数组的排序转化为两个子数组的排序
基本步骤：

1. 确定分界点的值x：q[l], q[(l+r)/2], q[r], 随机选择
2. 调整区间：[l, k] <= x <= [k+1, r]
3. 递归处理左右两段区间

难点：调整区间
暴力做法: 新开两个数组a b，遍历q将<=x的数插入a中>=x的数插入b中，将a b复制回q中
优美做法：采用两个指针i j, i指向>=x, j指向<=x，交换两个指针的值，直到相遇
因为要保证j i始终指向的值保持性质，采用先移动后比较，因此初始时位于数组外面

模板

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

    while (i < j) {
        while(q[++i] < x);
        while(q[--j] > x);
        if (i < j) {int t = q[i]; q[i] = q[j]; q[j] = t;}
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

注意点：

注意不是 <= x >= x,这样可能使得指针移动到边界，导致重复递归。

两类分配元素：

quick_sort(q, l, j);
quick_sort(q, j+1, j);

分界点不可采用q[r]，可采用q[l] q[l+r>>1]

quick_sort(q, l, i-1);
quick_sort(q, i, r);

分界点不可采用q[l]，可采用q[r] q[l+r+1>>1]

归并排序

基于分治的思想，但是是先递归再归并
基本步骤：

1. 确定分界点的位置 mid = l + r >> 1
2. 递归处理左右两端区间
3. 归并有序数组

难点：归并有序数组
使用双指针，分别指向两个数组的最小值，从而比较确定两个数组中的最小值，复制到新数组中，从而保证新数组的有序性

模板

public static void merge_sort(int[] q, int l, int r) {
    if (r <= l) return;
    int mid = l + r >> 1;

    merge_sort(q, l ,mid);
    merge_sort(q, mid + 1, r);

    int k = l, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] < q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];

    for (k = l; k <= r; k++) q[k] = temp[k];
}