AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

不优美_快排

作者: 作者的头像   幽梦影情结 ,  2022-11-24 18:55:06 ,  所有人可见 ,  阅读 172


3


事实就是,快排太难了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;
}

3 评论


用户头像
LL26cH   2022-11-24 18:58      2    踩      回复

现在你会快排了,但是吧解释写这样子写代码里,并不好看,还得拖一下进度条

用户头像
InvolutionZ   2022-11-24 19:24         踩      回复

%%%%%%%%

用户头像
幽梦影情结   2022-11-26 08:40         踩      回复

好!


你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息