快速排序

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;

int a[MAXN],n;

inline void Quick_read(int &x){//快读 
    int f = 1; x = 0 ; char ch = getchar();
    while((ch<'0'||ch>'9') && ch!='-') ch = getchar();
    if(ch == '-') f = -1,ch = getchar();
    while(ch>='0' && ch<='9') x = x*10+ch-'0',ch = getchar();
    x *= f;
}
inline void Quick_print(int x){//快输 
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) Quick_print(x/10);
    putchar(x%10+'0');
}
inline void p(){putchar(' ');}//输出空格 

void Quick_sort(int a[],int l,int r){//快排 

    if(l >= r) return ;

    int mid = a[l + r >> 1];
    int i = l , j = r ;

    while(i <= j){
        while(a[i] < mid) i++;
        while(a[j] > mid) j--;//不能取等 
        if(i <= j)   swap(a[i],a[j]), i++,j--;
    }
    Quick_sort(a,l,j);
    Quick_sort(a,i,r);
}
int main(){
    Quick_read(n);
    for(int i=1; i<= n ; i++)Quick_read(a[i]);
    Quick_sort(a,0,n);
    for(int i=1; i<=n ; i++ )Quick_print(a[i]),p();
    return 0;
}

• 注意mid一定要保存a数组的某个值(我就被坑了)

写成：

mid = l + r >> 1;
...
while(a[i] < a[mid]) i++;

是错误的，因为在排序的时候mid的值是固定的但是 a[mid] 可能会互换导致基准数改变