基数排序学习笔记

什么是基数排序

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

基数排序有什么用

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

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

她一般会在以下场景使用：

神题：WC[2017]挑战
对于排序复杂度比较敏感而数字又不怎么大的算法，如：后缀数组

基数排序怎么做

基数排序的原理

首先，我们可以先来了解以下基数排序的原理：如果给你一堆二位数，他们已经按个位数的大小排好了序，就像这样：

想象一下：如果我们按十位数大小排序，如果十位数大小一样，则按原有的顺序(之前已按个位数大小拍好的序)来排序，这个序列会变成什么样？

没错，这个数组最后会被我们排好序！

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

基数排序的具体做法

按照刚刚的原理，我们可以发现基数排序相当于把原数拆为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 后缀数组