Acwing 785.快速排序

本文是对y总算法基础课的学习记录。
今天学习的是快速排序模板
具体算法思想，y总有特别详细的解释，感兴趣的朋友可以去Acwing官网上看看，强推y总
原链接如下：
常用代码模板1——基础算法 - AcWing
快速排序算法模板：

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]//这里用的是用右移运算符 例如：a=a>>2 将a的二进制位右移2位 相当于该数除以2。
    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);
}

注意：

​ 这里存在边界问题，quick_sort(q,l,j),quick_sort(q,j+1,r);这里用的分界点是j，我们注意到第二个式子中为j+1，如果这时候我们一开始就把x设置成q[r]，则j指针j在一开始就满足不用移动的条件，停在那里（也即j=r），最后递归调用的时候，quick_sort(q,j+1,r);这个式子会return，无效；而这个式子quick_sort(q,l,j)由于j = r，即自己调用了和自己一模一样的参数的函数，会陷入死循环，不停地在调用自己

​ 同理，如果我们用的是i作为分界点，也即 quick_sort(q,l,i-1),quick_sort(q,i,r);则当初始x设置成q[l]的时候，分析步骤同上，同样也会出现死循环

​ 对于这种边界情况，比较好的记忆方法就是：x取左边界（q[l]）的话，我们用j和j+1来分；如果x取右边界（q[r]）的话，我们用i和i-1来分，但是最好的分法那肯定是x取中间，即q[l+r+1/2]，用位运算表示就是q[l+r>>1]

下面两种情况的推导，全部都可以用一个只含两个元素的数组的边界情况(如{1,2}这个数组)来推导，屡试不爽

while(i<j)时
如果是x = q[l + r +1>> 1]，用quicksort(q, l, i-1),quicksort(q, i, r);
如果是x = q[l + r>> 1]，用quicksort(q, l, j),quicksort(q, j+1, r);

while(i<=j)时
如果是x = q[l + r >> 1]，用quicksort(q, l, i-1),quicksort(q, i, r);
如果是x = q[l + r+1 >> 1]，用quicksort(q, l, j),quicksort(q, j+1, r);

整体代码如下：

#include<iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];

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);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}