快排的秘诀就是每一次确定一个数的位置然后我们就可以以这个数为分界点分成左边和右边在进行快排是nlog(n)
写代码的时候我们可以每一次都取l-1 r+1 然后每次找的时候先让他++或–这样是为了避免重复的数字出现从而死循环
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 100010;
int s[N] , n;
void quick_sort(int l , int r) {
if(l >= r) return ;
int i = l-1 , j = r+1 , x = s[(l+r)>>1];
while(i < j) {
while(s[++i] < x);
while(s[--j] > x);
if(i < j) swap(s[i] , s[j]);
}
quick_sort(l , j) , quick_sort(j+1 , r);
}
int main() {
cin>> n ;
for(int i = 0 ; i < n ; i ++) cin>>s[i];
quick_sort(0 , n - 1);
for(int i = 0 ; i < n ; i ++) cout<<s[i]<<" ";
}