基数排序学习笔记

什么是基数排序

基数排序是一个时间复杂度为:$O(n*MAXNUM/base)$,空间复杂度为$O(base+n)$的优秀排序算法。


基数排序有什么用

我们知道,桶排序可以在$O(MAXNUM)$的时间内,$O(MAXNUM)$的空间内排序一个数组,快速排序可以在$O(nlogn)$的时间内,$O(n)$的空间内排序一个数组。

如果有一个排序任务的最大数字比桶大,而数字数量又爆多怎么办?这时候,时空复杂度基于这两者之间的优秀排序:基数排序就闪亮登场啦~。

她一般会在以下场景使用:
1. 神题:WC[2017]挑战
2. 对于排序复杂度比较敏感而数字又不怎么大的算法,如:后缀数组


基数排序怎么做

基数排序的原理

首先,我们可以先来了解以下基数排序的原理:如果给你一堆二位数,他们已经按个位数的大小排好了序,就像这样:kjcfxg.png
想象一下:如果我们按十位数大小排序,如果十位数大小一样,则按原有的顺序(之前已按个位数大小拍好的序)来排序,这个序列会变成什么样?
没错,这个数组最后会被我们排好序!

在刚刚的推导过程中,我们显然可以发现:基数排序是一个不稳定的排序

基数排序的具体做法

按照刚刚的原理,我们可以发现基数排序相当于把原数拆为base进制数(base为我们选定的一个基数,在刚刚的例子中,base=10),然后按位排序。
那我们具体怎么实现呢?

我们可以考虑用桶排序来实现每位排序的功能。
我们先把每个数在当前位下的那个数全部丢到一个桶里面,然后对这个桶做前缀和

int cnt[10]={0};
for(int i=1;i<=n;i++)
    cnt[(a[i]/exp)%10]++;
for(int i=0;i<=9;i++)
    cnt[i]+=cnt[i-1];

然后,我们从后往前去把所有的数看一遍,这个数当前的排名即为他所在的桶的值,然后把这个桶的值-1。(因为我们可以保证之前的排序中在前面的数一定比在后面的数小)

for(int i=n;i>=1;i--)
    b[cnt[(a[i]/exp)%10]--]=a[i];
for(int i=1;i<=n;i++)
    a[i]=b[i];

然后,我们在外面再套一层枚举位数的就搞定啦~

void count_sort(int a[],int n,int exp)
{
    int cnt[10]={0};
    for(int i=1;i<=n;i++)
        cnt[(a[i]/exp)%10]++;
    for(int i=0;i<=9;i++)
        cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)
        b[cnt[(a[i]/exp)%10]--]=a[i];
    for(int i=1;i<=n;i++)
        a[i]=b[i];
}
void radix_sort(int a[],int n)
{
    int MAX=0;
    for(int i=1;i<=n;i++)
        MAX=max(a[i],MAX);
    for(int i=1;i<=MAX;i*=10)
        count_sort(a,n,i);
}

有啥题目练啊

WC2017 挑战的第一个subtask
后缀数组

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注