快速排序

参考题目：

Acwing 785.快速排序

Acwing 786.第k个数

快排思路——分治思想：

1. 确定分界点：q[l] 、 q[l+r/2] 、 q[r] 或随机点，一般选择q[l+r/2]

2. 调整区间：将区间根据分界点划分为两部分，左边那部分小于等于分界点，右边那部分大于等于分界点

3. 对划分的区间进行递归操作

易错点：

• 双指针操作部分，只可以使用do while而不能使用while do

因为在交换之后左右指针需要先改变再判断所以要先do后while，不然遇到相等情况，则会进入无限循环。

例：头尾指针还有分界点的值相等：{2,2}

• 递归排序的时候选用i或选用j作为递归的参数跟mid向上或向下取取整是有关系的。

向上取整要使用i：quick_sort(a, l ,i-1);quick_sort(a,i,r);

向下取整要使用j：quick_sort(a, l ,j);quick_sort(a,j+1,r);

例：两个数的时候，如：{1,2}

要说明两点：

1. 最后左右指针停留的位置。有两种情况：

   第一种：如果序列个数为偶数，那么左右指针是交叉的

   第二种：如果序列个数为奇数，那么左右指针为重合的

2. mid的取值，向上跟向下取整，对于特例：区间只有两个数的时候

   向下取整mid指向第一个数，上取整指向第二个数

说明向下取整的使用i指针出错的情况：

区间[1,2]，最后左右指针停留的位置在1

所以左边界为使用i表示为：[l,i-1] = [1,0]
右边界：[i,r] = [1,2] 跟之前一样，对[1,2]进行划分之后还是[1,2]所以右区间会进入无穷循环

同理，向上取整，且取右边界也会发生同样的情况

易错点总结：

1. 交换之后指针要改变，所以使用do while。例：头尾指针还有分界点的值相等：{2,2}
2. 区间结束后头尾指针不是重叠就是交叉，区间判断跟分界点取值上下取整有关。例：只有两个数的时候：{1,2}

代码

#include<iostream>
using namespace std;
const int N = 100010;

int a[N];
void quick_sort(int a[],int l,int r)
{
    //递归终止条件，区间为一个数的时候
    if(l >= r)return ;
    // 确定分界点，左右指针初始化
    int mid = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    // 调整区间：左区间<= mid   右区间>= mid
    while(i < j)
    {
        do i++; while(a[i] < mid);//寻找不符合左区间的值
        do j--; while(a[j] > mid);//去渣不符合有区间的值
        if(i < j)swap(a[i], a[j]);//交换
    }
    quick_sort(a, l ,j);//递归对左区间进行排序
    quick_sort(a,j+1,r);//递归对右区间进行排序
}

int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)scanf("%d",&a[i]);

    quick_sort(a,0,n-1);

    for(int i = 0; i < n; i++)printf("%d ",a[i]);
    return 0;
}