AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

2-2 快速排序

作者: 作者的头像   Eric2020 ,  2020-05-22 19:39:13 ,  阅读 193


2


例1 快速排序

此题数据量非常大,前面的算法都不奏效。这次介绍最普遍的算法——快速排序。
其实挺简单的,但需要理解语言中的递归部分。
大致过程是对于一个无序序列,找到一个数(后面简称x),将序列中比x小的数放在左边,比x大的放在右边,
然后对左右用同样的操作,直到操作完成。
怎么选x呢?随便选。对,你没听错,就是随便选。。。
选好后,左边找到第一个比x大的,右边找到第一个比x小的,交换;
继续进行相同的操作……实现如下:

void qsort(int a[],int l,int r)
{
    int i=l,j=r,flag=a[(l+r)/2];
    do
    {
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j)
            swap(a[i],a[j]);
    }while(i<=j);
    if(l<j) qsort(a,l,j);
    if(i<r) qsort(a,i,r);
}

在极端情况下,快排时间复杂度是O(n^2),但如果随机选x,很难出现这种。
实际上随机的算法复杂度为O(nlogn),空间复杂度是O(n)。快排还利用了“分治”思想,
后面还会介绍归并排序。


例2 第k个数
虽然可以先排一遍,直接定位第k个,但算法复杂度为O(nlogn)。
借鉴分治思想,可降到O(n)。和快排一样,任意取x,左边的部分不大于右边。
k在哪边就递归哪边,都不属于可直接给出答案,代码如下:

int ans=0,k;
void findkth(int a[],int l,int r)
{
    if(l==r)
    {
        ans=a[l];
        return;
    }
    int i=l,j=r,flag=a[(l+r)/2];
    do
    {
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;j--;
        }
    }while(i<=j)
    if(k<=j) findkth(a,l,j);
    else if(i<=k) findkth(a,i,r);
    else findkth(a,j+1,j-1);
}

END

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息