事实就是,快排太难了2333(笑
快排就是分治嘛,以一个数为边界,分两边,一直分,一直排,排到最后一层有效的两个数,顺序也就出来了。
边界确实有点恶心,好吧,一年前的我也没有把题解吃透吧hh
我们要做的就是使得分治得两个区间内部不一定有序,但总体满足一个性质,左边的数<= x
,右边的数>=x
,这个x
理论上取序列中哪个值都是可以的。但是取的不好也会影响递归的层数,往下看吧(笑
理论上如果我们每次以区间中间的数为边界进行递归,那最多就logn
次,分成的同一层的区间,第一层是[0, n - 1]
, 第二层是[0, n / 2 - 1], [n / 2, n - 1]
, 第三层就是四份嘛,每一份在扫面过程中至多扫描n/(2 ^ t - 1)
次, t
为层数,所以每一层还是O(n)
的时间复杂度,总的时间复杂度是O(nlogn)
至于O(n^2)
,还是得模拟啊2333,恰好找到的数是最大的话,就会嘎嘎递归了
那就来模拟一下吧(笑
10
个数
49 59 88 37 98 97 68 54 31 3
按照模板int x = a[l + r >> 1];
取中间的数,会取到98
这是最大的数,所有的数都是小于等于它的
do ll++; while(a[ll] < x);
do rr--; while(a[rr] > x);
ll
指针会一直走到98
所在的位置,数组下标为4
,而rr
指针因为do while
循环动一次指到3
,数组下标为9
,这一轮循环结束后
49 59 88 37 3 97 68 54 31 98
quick_sort(a, l, rr), quick_sort(a, rr + 1, r);
可以发现rr
和r
相等,都是9
,所以没有实现分治的目标。
进入下一次递归,rr
指针至少左移一个位置,因为上一次循环已经把最大的移到最右边了,如果找的的数又是剩余的数(除去98
最大的),那rr
指针只会左移一个单位。这样又等价于没实现分治,这样就会有n
次“递归”,时间复杂度就是O(n^2)
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
int n, cnt;
void quick_sort(int a[], int l, int r){
if(l >= r) return;
int ll = l - 1, rr = r + 1;
int x = a[l + r >> 1];
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for(int i = l; i <= r; i++){
if(a[i] > x) c[cnt2++] = a[i]; // b, c为辅助数组嘛
else if(a[i] < x) b[cnt1++] = a[i];
else cnt3++;
}
int k = l;
for(int i = 0; i < cnt1; i++)
a[k++] = b[i];
for(int i = 0; i < cnt3; i++)
a[k++] = x;
for(int i = 0; i < cnt2; i++)
a[k++] = c[i];
if(cnt3 > 1) cnt3 /= 2; //保证分的区间至少有一个数,否则陷入死循环,边界问题出不来了
//如果分的一段区间是相同的数,我们要保证能继续分治下去
//为什么取中间的数呢,分治嘛,这样分的少,hack数据,都是同一个数
//可以用下面注释的代码打打表看看
quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3 , r);
//cnt++;
//cout<<l<<" "<<l+ cnt1 + cnt3 - 1<<" "<<r<<" "<<x<<endl;
// for(int i = l; i <= r; i++)
// cout<<a[i]<<" ";
// cout<<endl;
// if(cnt < 10)
// quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3, r);
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)
cin>>a[i];
quick_sort(a, 0, n - 1);
for(int i = 0; i < n; i++)
cout<<a[i]<<" ";
return 0;
}
现在你会快排了,但是吧解释写这样子写代码里,并不好看,还得拖一下进度条
%%%%%%%%
好!