53 基数排序与桶排序：如何通过分配和收集进行排序？

你好，我是王健伟。

上节课我带你学习了桶思想排序中的计数排序，这节课我再带你学习一下另外两种桶思想排序——基数排序、桶排序。我们先从基数排序开始讲起。

什么是基数排序？

以往的排序主要是通过关键字的比较和记录的移动来进行。而基数排序是一种不同以往的排序方式，它并不需要进行关键字的比较。

基数排序要进行多趟排序，每趟排序都要经历“分配”和“收集”两个步骤，当然，每趟排序也都会基于上一趟排序的成果再次排序。

有这么一组数字 {516,231,445,323,299,2,18,67,42,102,164,755,687,437} 。现在希望对这组数字进行从小到大的排序。观察一下这组数字，最大的数字也就是3位（个位、十位、百位），所以为了更清晰地说明算法，可以把这组数字都扩展成3位的，比如 {516,231,445,323,299,002,018,067,042,102,164,755,687,437} 。

将关键字拆分成d组（上面范围每个数字都是3位，所以将要拆分成3组，即d=3），然后按关键字位的权重递增的次序（个位、十位、百位）来做d趟的“分配”和“收集”动作。

因为“个位”、“十位”、“百位”数字取值都是0_{9（10个数字）之间，所以建立10个辅助队列（桶）B0}B9来保存个位、十位、百位信息。

第一趟处理取权重最低的即“个位”进行“分配”和“收集”两个动作，如图1所示。

分配：以“个位”数字进行分配，将指定数字放到辅助队列B0~B9中，比如对于数字516，其个位数字是6，所以放入到B6中。其余数字也是如此处理。对于个位数字重复的，在相应的辅助队列中从上到下依次放置。
收集：依次从B0~B9辅助队列中把相关的数字从上到下、从左到右收集并排列起来。
这样就得到了按“个位”递增排序的数字序列。

第二趟处理取“十位”进行“分配”和“收集”两个动作，第二趟处理会基于第一趟处理的成果进行，如图2所示。

分配：以“十位”数字进行分配，将指定数字放到辅助队列B0~B9中，比如对于数字231，其十位数字是3，所以放入到B3中。其余数字也是如此处理。对于十位数字重复的，在相应的辅助队列中从上到下依次放置。不难发现，在相同的队列中，个位数越小越是在队头位置。
收集：依次从B0~B9辅助队列中把相关的数字从上到下、从左到右收集并排列起来。

这样就得到了按“十位”递增排序的数字序列。对于“十位”数字相同的，“个位”数字按递增排序。

第三趟处理取“百位”进行“分配”和“收集”两个动作，第三趟处理会基于第二趟处理的成果进行，如图3所示。

分配：以“百位”数字进行分配，将指定数字放到辅助队列B0~B9中，比如对于数字002，其百位数字是0，所以放入到B0中。其余数字也是如此处理。对于百位数字重复的，在相应的辅助队列中从上到下依次放置。
收集：依次从B0~B9辅助队列中把相关的数字从上到下、从左到右收集并排列起来。

这样就得到了按“百位”递增排序的数字序列。对于“百位”数字相同的，“十位”数字按递增排序。如果“百位”和“十位”数字都相同，则会按“个位”递增排序。

实现代码如下。

//基数排序
template<typename T>
void RadixSort(T myarray[], int length)
{
    if (length <= 1) //不超过1个元素的数组，没必要排序
        return;

    T* pResult = new T[length]; //新数组，用于保存每趟排序的结果

    //借用C++标准库中的list容器保存必要的信息，当然也可以用自己写的链表来保存数据
    std::list<T *> mylist[10]; //#include <list>  ，注意list中的<>里的数据类型

    //3，意味着分别取得个位、十位、百位 数字
    for (int i = 0; i < 3; ++i) //为简化代码，假设已经知道待排序数字最大不超过3位，所以这里就直接写i < 3了
    {
        //(1)分配
        for (int j = 0; j < length; ++j)
        {
            //根据i值来决定取得某个数字的个位、十位、百位
            int tmpi = i;
            T tmpvalue = myarray[j];
            T lastvalue;   //取得的个位、十位、百位数字保存在这里
            while (tmpi >= 0)
            {
                lastvalue = tmpvalue % 10;
                tmpvalue /= 10;
                tmpi--;
            } //end while

            mylist[lastvalue].push_back(&myarray[j]);  //在list尾部插入元素
        } //end for j

        //(2)收集
        int idx = 0;
        for (int k = 0; k < 10; ++k)
        {
            for (auto iter = mylist[k].begin(); iter != mylist[k].end(); ++iter)
            {
                pResult[idx] = *( * (iter));
                idx++;
            } //end iter
            mylist[k].clear(); //清空mylist,为下次向其中存数据做准备
        } //end for k

        //(3)把数据拷贝回myarray
        for (int m = 0; m < length; ++m)
        {
            myarray[m] = pResult[m];
        }//end for m
    } //end for i

    delete[] pResult;
    return;
}

在main主函数中，代码应该是这样的。

int arr[] = { 516, 231, 445, 323, 299, 2, 18, 67, 42, 102, 164, 755, 687, 437 };
int length = sizeof(arr) / sizeof(arr[0]);   //数组中元素个数
RadixSort(arr, length);//对数组元素进行基数排序
cout <<"基数排序结果为：";
for (int i = 0; i < length; ++i)
{
    cout << arr[i] <<"";
}
cout << endl; //换行

下面是代码的执行结果。

基数排序算法效率分析

基数排序算法时间复杂度分析：假设算法进行了d趟的分配和收集，每趟分配要扫描待排序的n个元素，所以每一趟分配的时间复杂度是O(n)。此外还需要用到多个辅助队列进行分配完后的数据收集工作，假设用到的是k个辅助队列，所以每趟收集的时间复杂度是O(k)。所以总的时间复杂度是O(d(n+k))。

从代码可以看到，基数排序需要一些辅助空间来保存数据。

比如这段代码行。

T* pResult = new T[length];
std::list<T *> mylist[10];

这段代码用到的队列数组有k（10）个，所以空间复杂度是O(n+k)。此外，基数排序算法是稳定的，你只要结合代码，拿两个相同的数字画一画或稍微想想就可以得出结论。

基数排序算法的应用

前面实现的算法代码是针对一系列数字进行从小到大的排序。当然，基数排序还有许多适用场合。

举个例子，某学校有5000名学生，他们的出生日期有详细记录，要求将学生按照年龄从小到大排序。

要完成这个需求，根据学生的出生日期来确定排序次序是非常合适的，可以把每个学生的出生日期拆解为年、月、日三部分。已知学生的出生日期在1990_{2010年之间，月份自然是在1}12之间，日期在1~31之间。

从权重的角度来看，年>月>日，所以，排序的时候应该是先按照日来排序，再按照月来排序，最后按照年来排序。

考虑到按照年龄从小到大排序，所以日这一项应该从大到小排序（日这个数字越大的人年纪越小）。

看一看第一趟先对日这一项进行排序，如图4所示。

第二趟要针对月这一项进行排序，这一项也应该从大到小（月这个数字越大的人年纪越小），如图5所示。

第三趟要针对年这一项进行排序，这一项也应该从大到小（年这个数字越大的人年纪越小），如图6所示。

经过上述三趟的分配和收集操作，就可以得到学生按照年龄递增的排序。从这个范例中可以看到，每趟处理所采用的辅助队列大小是可以不同的。

根据前面的分析，基数排序算法的时间复杂度是O(d(n+k))。里面的字母都是什么意思呢？

d表示趟数，这里是3。
n是5000，因为参与年龄排序的学生是5000名。
k是每趟排序用到的辅助队列大小，第一趟是31，第二趟是12，第三趟是21，这里按最大值31计算。
把d、n、k代入时间复杂度公式O(d(n+k)) ≈ O(15093)。相比于一些其他时间复杂度的排序算法比如O($n^{2}$) ≈ O(25000000)或者O(n$log_{2}^{n}$) ≈ O(60000)来说，基数排序算法的时间复杂度表现非常好。

理解基数排序的应用之后，我们尝试总结一下它的适用场合。

记录中要排序的关键字可以很方便地拆分成几组，比如上述范例的年、月、日是三组。组数当然也不能太大，因为每多一组就代表多一趟分配和收集处理。
每组关键字的取值范围也不应该太大，比如上述范例年月日的取值范围都不算大。否则算法需要的辅助空间也会太大导致空间复杂度过高。
待排序记录数量多多益善，记录数量多意味着要排序的元素数量n较多。如果待排序记录很少，则没有必要用基数排序，基数排序毕竟需要不少的辅助空间，杀鸡焉用牛刀。

什么是桶排序（Bucket Sort）？

桶排序有时也叫箱排序。当要排序的数据分布比较均匀时适合采用桶排序。

其实，往往可以把前面讲解的计数排序和基数排序看成是桶排序的特殊情形。而这里讲解的桶排序往往指的是一般情形。一般情形的桶排序比较少用，而且单个桶内的数据排序需要进行关键字的比较，你做个简单了解即可。

假设有n个要排序的数据放在数组中。

首先遍历这个数组，求出数据中最小值比如是0和最大值比如是1000，假设这些数据比较均匀地分布在0_{1000这个范围内。那么桶排序的思想是把0}1000这个区间划分成若干个（比如4个、5个、10个等都可以）大小相同的子区间，这些子区间可以称为“桶”。

比如0_{250是第一个区间，251}500是第二个区间，501_{750是第三个区间，751}1000是第四个区间。然后将要排序的数据放入到适合自己大小的桶中。因为前面做了要排序数据分布比较均匀这种假设，所以一般不会出现各个桶中数据量差异很大的情形。然后需要先对各个桶中的数据进行排序，再按桶的次序把各个桶中的数据输出出来即可。

这里以 {12,18,0,91,40,66,78,89,6,27,39,22,31,55,52,97,62,45,11,80} 这组待排序的数据进行说明。

上面这组数据的范围在0_{100之间，所以可以把这个区间划分成4个（该数字比较随意）大小相同的子区间（4个桶）：0}25、26_50、5175、76~100。然后把这些待排序的数据根据自身大小放入对应的桶中。如图7所示。

同一个桶中的数据可以采用数组、链表等数据结构存储。针对每一个桶中的数据进行单独的从小到大排序，再按桶的次序（从左到右）把各个桶中的数据输出出来，如图8所示。

不过，桶排序会涉及一些问题。

待排序数据如果分布不均匀，就会导致有的桶中数据很多，有的桶中数据很少，甚至有的桶中没有数据的情形。
每个桶中数据如何存储（比如是使用数组还是链表）以及桶中数据如何排序的问题。

如果用数组存储桶中数据，那么数组设置多大合适呢？如果采用可以扩容的数组，存满数据时将申请更大的内存空间，将整个数组搬到该内存空间，那么无疑会影响算法效率，而如果采用固定大小数组，那么数组就得设置为能够容纳所有待排序数据的大小，就会很浪费内存。如果采用链表，那么对桶中数据进行排序就会很不方便，时间复杂度会很高。

每个桶中的数据可以采用归并排序、快速排序等手段进行排序。

总之，桶排序是一种用空间换取时间的排序算法。这个算法是有一些使用限制的，要求待排序的数据均匀分布，桶的个数要设置合理以避免空桶的产生。

桶排序算法的实现代码我在这里就不提供了，并不复杂，有兴趣的话你可以自行编写。

桶排序算法复杂度分析

我们先来梳理一下桶排序的时间复杂度。

遍历n个元素的数组（n次循环），求数据中最小值和最大值来决定桶的数量和每个桶中保存数据的范围。这个时间复杂度为O(n)。
遍历n个元素并装到桶中（n次循环），所以这一步的时间复杂度为O(n)。
假设共有k个桶(大概每个桶中平均有$\frac{n}{k}$个元素)，k次循环对每个桶中的数据排序。如果采用快速排序方式(算法的时间复杂度为O(n$log_{2}^{{n}$))，这里的n应该用$\frac{n}{k}$来代替，因为$\frac{n}{k}$才是桶中元素个数，所以快速排序算法时间复杂度为O($\frac{n}{k}$$log_{2}}}{k}}$)，所以所有桶中数据排序的总时间复杂度为O(k$\frac{n}{k}$$log_{2^{{\frac{n}{k}}$)，即O(n$log_{2}}$)。}{k}
结果输出的时间复杂度也是O(n)。
所以整个算法时间复杂度是O(n+n$log_{2}^{\frac{n}{k}}$)。
如果使用n个桶并且待排序值分布很均匀，此时可以避免桶内数据排序，此时的时间复杂度接近O(n)，此时的排序就等于是计数排序了。
如果数据全部放到一个桶去那就是最差的情况了，此时桶排序的时间复杂度就退化到O(n$log_{2}^{n}$)了。

其实，桶排序算法的时间复杂度说法不一，因为内部使用的数据结构不同，实现代码不一样等。另外因为有k个桶，也涉及对 k个桶初始化，所以有些资料上给的算法时间复杂度是O(n+k+n$log_{2}^{\frac{n}{k}}$)等。其实这些答案各有道理，并不建议你深究，因为本身时间复杂度也是一个估算值，既然是估算，就肯定不会非常精确。

桶排序的空间复杂度大概为O(n+k)。一般来说，如果算法的时间复杂度有所改善，那么算法的空间复杂度一般就会增加。

桶排序算法的稳定与否取决于对同一个桶中数据的排序所采用的排序算法是否稳定，比如采用快速排序，则桶排序算法是不稳定的，如果采用归并排序，则桶算法是稳定的。

小结

本节课我为你讲解了桶思想排序中的基数排序和桶排序两种排序算法。

基数排序不需要进行关键字的比较，但需要进行多趟排序。每趟排序都要经历“分配”和“收集”两个步骤，每趟排序都会基于上一趟排序的成果再次排序。我为你详细阐述了基数排序的思想、步骤和实现代码，为你详细分析了算法的执行效率以及算法的适用场合。

桶排序适合要排序的数据分布比较均匀时采用。我为你讲解了桶排序的基本概念、并对该算法的复杂度进行了分析。该排序算法的稳定性取决于对同一个桶中数据的排序所采用的排序算法是否稳定。

最后，我也为你整理了一下各种桶思想排序算法的时间复杂度、空间复杂度、算法稳定性表格供你参考。

思考题

在这节课的最后，我也给你留了几道复习思考题。

请你尝试实现桶排序算法。
仔细想一想什么时候使用基数排序算法、桶排序算法？
尝试举一组数来描述使用基数排序对这组数据进行排序的步骤。

欢迎你在留言区和我互动。如果觉得有所收获，也可以把课程分享给更多的朋友一起学习。我们下节课见！