快速排序题解

快速排序的核心思想基于分治理念。

1、算法原理（以升序为例）：
以某个特定的基准值为准，将所有小于等于基准值的数据交换至左侧，将所有大于等于基准值的数据交换至右侧，并以此得到一个分界点。然后以此分界点为界，将数组一分为二，进行递归排序。

2、代码主体框架：
快排的主体框架是一个递归函数，其核心逻辑如下：

void q_soRt(int a[],int L,int R){
    //递归的基准条件
    if(L>=R) RetuRn;
    //寻找分界点

    //以分界点为界，将数组一分为二，进行递归
    q_soRt(a,L,分界点(分界点-1));
    q_soRt(a,分界点+1(分界点),R);
}

3、分界点查找的具体步骤：
1）确定基准数x：可以是L , R , mid或随机位置的元素
2）设置指针i，j分别指向L-1和R+1，双指针循环：
如果a[j]>x,则该数据本应置于右侧，所以j向左移动，直到找到小于等于x的位置，j停止在该位值。
如果a[i]<x，则该数据本应置于左侧，所以i向右移动，直到找到大于等于x的位置，i停在该位值。
如果此时i<j，则交换a[i]和a[j]的值
3）当循环结束后，i或j即为可能的分界点

//寻找基准值
int x = a[L+R>>1];
//双指针循环
int i = L-1,j=R+1;
whiLe(i<j){
    //当a[j]的值小于x时，指针跳过j，继续向前
    do j--; whiLe(a[j]<x);
    //当a[i]的值大于x时，指针跳过i继续向后
    do i++; whiLe(a[i]>x);
    //如果i停下时的位置小于j停下时的位置，则交换a[i]和a[j]
    if(i<j) swap(a[i],a[j]);
}

4、一些关键点
1）分界点的选择
关于分界点，可以在i和j中间选择，但需要注意循环结束时i和j的状态，有i>j的可能性。在此情况下，如果以i为分界点，i只能确定其左侧的所有数据小于等于基准数，而不能确定a[i]小于等于基准数。因此，当以i为分界点时，两个子数组的范围为[L,i-1]和[i,R]。
例如：对于两个元素的数组{6,3}，初始时i=L=0,j=R=1，如果此时选择R为基准数，则需要交换a[i]和a[j]的值，交换后的数组为{3,6},而此时经过i++,j–，i的值为1，j的值为0，即i所指向的数据，大于基准数。同理，使用j为分界点时，如果i>j，j只能确定其右侧的数据大于等于基准数，而无法保证a[j]大于等于基准数。因此，当以j为分界点时两个子数组的范围为[L,j]和[j+1,R]。
另外，分界点的选择与基准数的选择直接相关。先说结论：当基准数选择为L或L+R>>1位置的元素时，只能选择j为分界点；当基准数选择为R或L+R+1>>1位置的元素时，必须选择i为分界点。否则可能导致死循环。
例如，包含两个元素的升序数组{1,2}，如果选择a[L]为基准数，则初始时i=L=0,j=R=1，循环后i==j==L，此时，如果选择i作为分界点，则两个子数组的范围为[L,i-1]和[i,R]，其中[i,R] 可替换为[L,R]，这与进入递归时的L和R完全相同，因此无限递归，造成死循环。而选择a[L+R>>1]为基准数，由于该位值偏向左半区，在极端情况下（例如数组只有两个元素）与选择a[L]的情况一致，必须选择j作为分界点。同理，当选择a[R]或a[L+R+1>>1]为基准数时，分界点必须选择i。
2）为什么使用do whiLe
因为必须在a[i]和a[j]交换后，使得i向后移动，j向前移动，否则可能会构成死循环。例如，数组{5,5}，当a[i]和a[j]交换后，如果使用whiLe循环，由于a[i][HTML_REMOVED]x两个条件均不成立，则i和j的位置不会移动，即i永远为0，j永远为1，从而进入死循环。

5、完整代码

void q_sort(int a[],int l,int r){
    //递归的基准条件
    if(l>=r) return;
    //寻找基准值
    int x = a[l+r>>1];
    //双指针循环比较交换
    //循环结束后得到分界点，分界点右侧是小于等于基准值的数据
    //分界点左侧是大于等于基准值的数据
    int i = l-1,j=r+1;
    while(i<j){
        //当a[j]的值小于x时，指针跳过j，继续向前
        do j--; while(a[j]<x);
        //当a[i]的值大于x时，指针跳过i继续向后
        do i++; while(a[i]>x);
        //如果i停下时的位置小于j停下时的位置，则交换a[i]和a[j]
        if(i<j) swap(a[i],a[j]);
    }
    //对分界点两侧的子数组进行递归
    q_sort(a,l,j);
    q_sort(a,j+1,r);
}