快排思考

1. C++模板代码

#include<iostream>
using namespace std;

const int N=1e6+10;
int a[N];

void quick_sort(int a[], int l,int r){
    if(l>=r) return;
    int x=a[l], i=l-1,j=r+1;
    while(i<j){ 
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j) swap(a[i],a[j]);
    } //i>j？  i==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]);
}

刷剑指offer时，调整数组使奇数位于偶数之前，用到了双指针做法的思想，但是注意到while(i<=j)
https://www.acwing.com/problem/content/30/
于是产生了一下几个问题？

1. while(i<j) 和 while(i<=j)用法上有什么区别？
2. 快排再思考，注意到循环里两个while()的条件并不全面
3. 快排什么时候退出条件i==j,什么时候i>j? 
4. 快排基本条件if(i>=j) 

经过实践，发现模板代码的逻辑是：
如果找到大于或小于不满足的，交换过后，下一次就跳过这两个的判断

而这样就会产生问题，出现i>j的问题，所以这里将模板代码修改了一下

void quick_sort(int a[], int l,int r){
    if(l>=r) return;
    int x=a[l], i=l,j=r;
    while(i<j){ 
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if(i<j) swap(a[i],a[j]);
    } //退出条件一定是i==j
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
}

还有在这里循环里的条件不能改变，即只有大于和小于;这样实际的执行行动中，i和j只会有一个指针活动，但是也保证了i,j不会出现i>j的情况

同时也需要注意的是
x=a[l]时, i,j会同时等于l, 所以递归[l,j],[j+1,r]
x=a[r]时，i,j会同时等于r, 所以递归[1,j-1],[j,r]
其他任意。

因为i,j保证一直在l,r中间，所以基本条件的判断只需要是if(i==j)即可

然后还有一个while(i<=j){} 和while(i<j){}
调整奇数偶数题循环内部的条件加起来是全部，所以i==j时还能进一步运行
快排题循环内部的条件没有a[i]==x的判断，所以会一直停在i==j不动，所以不能加i==j

总结

改进后的模板更好，体现了快排一次划分，能够保证用于划分的元素在最终位置上，而yxc大佬给的模版不能保证这个性质，如
3 4 1 2 5 6
选x=a[0]=3;
第一次划分得到的是 2 1 4 3 5 6, 3并没有在最终位置上。

交流

这种做法会引起超时的行为，待对时间复杂度进行进一步的思考
30
128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216

更新，这种超时行为时因为遇到了3 1 2 4 3这种例子，当a[i]=x, a[j]=x并且i<j, 这里会一直陷入循环跳不出去！所以不能这样更改