快速排序

快速排序

双指针 分治

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

边界情况分析参考：https://www.acwing.com/solution/content/16777/

1. 以j为划分时，x不能选q[r] 或 若以i为划分,则x不能选q[l]
2. do i++; while(q[i] < x)和do j--; while(q[j] > x) 中不能用q[i] <= x 和 q[j] >= x
3. if(i < j) swap(q[i], q[j])可以使用 i <= j
4. 最后一句不能改用quick_sort(q, l, j-1), quick_sort(q, j, r)作为划分
5. j的取值范围为[l..r-1]
6. while(i < j) 不能改为 while(i <= j)