基数排序

bangbang-ande

基数排序——基数排序也是计数排序的升级版，这一个排序的方法很巧妙，相信听完这一部分之后一定有收获。
基数排序依旧有桶排序的影子，同样需要用到桶：

                               
登录/注册后可看大图

但是基数排序的桶的数量是固定的，就是10个桶。我们讲的时候大家就明白了。
举一个例子：

下标	0	1	2	3	4	5	6	7	8	9
a[]	94	27	12	9	125	30	55	40	73	65

第一步，初始化，建立10个桶+将数字存入数组中

                               
登录/注册后可看大图

第二步，我们先看每一个数的个位，把个位的值对应到相同的数字中：（这里所使用的存法是链表，但实际打代码的时候可以不用用链表）

                               
登录/注册后可看大图

然后下一步也很简单，将我们放在桶中的数据重新放回数组中，此时有人问：怎么放呢？其实是这样的：我们将桶从小到大循环，将桶中的数据依照放入的顺序重新放入数组中，然后清零桶，得到这样子：

                               
登录/注册后可看大图

此时已经完成了第一次操作，但实际上大家可能没有发现排完的数据有序在哪里，那我们继续进行第二次相同的操作，但注意，我们接下来比对十位，如果数只有一位，那就十位是0。同样将对应数字加入桶中：

                               
登录/注册后可看大图

下一步同样类比操作，存入数组中，存后的图如下：

                               
登录/注册后可看大图

此时的程序就基本有序了，然后继续进行操作，下一步的操作大家自行完成。最后就得到一个排好序的序列了。

这就是基数排序的做法了，总结下来就3步：第一步从个位数开始循环，循环到所有位数都循环完，然后在循环内部进行两步操作，一步是将对应数字加入桶中，第二步是将桶里的数字从小到大重新取回数组中。
接下来我们根据这几步写出来核心代码：

//这一部分可在附件中看到

整一段代码分为三部分：
1-4为第一部分，6-16为第二部分，18-25是第三部分
这三部分的大概作用其实在注释中已经说明得很清楚了。

解决一下注释中的两个问题：
Q1：这一段的内容其实是找出这个数的某一位。无论是个位，十位，百位，找法都是这样子，大家可以代入几个数字试一试，就可以明白了
Q2：这段代码一定不能删，因为如果不删去，之前的数字残留，会影响到下一次的遍历
所以这段代码的讲解就大约这样子。

接下来是完整代码：

//这一部分可在附件中看到

最后说说该排序的特性：
1. 一样的，本排序一定是不稳定排序，理由是运用了计数排序的做法，当然是不稳定的排序
2. 本排序的时间复杂度为O(n+n log lmax)≈O(n)，推断方法很简单：
   加入对应桶中的时间复杂度为O(n\log lmax)，而将排好的桶放在数组中的时间复杂度为O(n)
   所以时间复杂度为O(n+n log lmax)

zhangjinxuan

之前我写过基数排序，现在除了在卡常的时候都不会用

zhangjinxuan

上一个比较拙劣的基数排序：

int getw(int num, int w)
{
        while (--w)
                num /= 10;
        return num % 10;
}
void rsort(int * a,int len)
{
        static int tmp[maxs];
        int maxnum = -1 << 30, w = 0;
        for (int i = 0; i < len; ++i) maxnum = max(maxnum, a[i]);
        while (maxnum) {
                maxnum /= 10;
                w++;
        }
        for (int i = 1; i <= w; ++i) {
                int cnt[10] = {};
                for (int j = 0; j < len; ++j)
                        cnt[getw(a[j], i)]++;
                for (int i = 1; i < 10; ++i)cnt[i] += cnt[i - 1];
                for (int j = len - 1; j >= 0; --j)
                        tmp[--cnt[getw(a[j], i)]] = a[j];
                for (int i = 0; i < len; ++i)
                        a[i] = tmp[i];
        }
                
}

1 年前写的代码，好丑