计数排序

　　有这样一道排序题：数组里有20个随机数，取值范围为0~10，要求用最快的速度把这20个整数从小到大进行排序。第一时间有人可能会想使用快速排序，因为快速排序的时间复杂度只有O(nlog2n)。但是这种方法还是不够快，有没有比O(nlog2n)更快的排序方法呢？有人可能会有疑问：O(nlog2n)已经是最快的排序算法了，怎么可能还有更快的排序方法？

　　这里先来回顾一下经典的排序算法，无论是归并排序、冒泡排序还是快速排序等，都是基于元素之间的比较来进行排序。但是有一种特殊的排序算法称为计数排序，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

　　在刚才的题日里，随机整数的取值范围是0~10，那么这些整数的值肯定是在0~10这11个数中。于是程序里可以建立一个长度为11的列表，列表下标为0~10，元素初始值全为0，如下图所示。

　　假设20个随机整数的值是：arr=[9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9]。

　　遍历这个无序的随机数组，每一个整数按照其值对号人座，对应数组下标的元素进行加1操作。比如第1个整数是9，那么数组下标为9的元素加1，如下图(b)所示。第2个整数是3，那么数组下标为3的元素加1，如下图(c)所示。继续遍历数组并修改，最终数组遍历完毕时，数组的状态如下图(d)所示。

　　计数排序适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(n1og2n)的排序，例如快速排序、归并排序等。当然这是一种牺牲空间换取时间的做法，而且当取值范围大而分散且数量很多时其效率反而不如基于比较的排序。
　　计数排序的时间复杂度（平均）是O(n+k)，空间复杂度是O(n+k)，为稳定性排序算法。

　　程序代码：

　　运行结果

　　练习题１：产生40个0≤n≤20的随机数列表，然后用计数排序法把它们排序。

　　桶排序

　　桶排序是计数排序的升级版，其逻辑算法：假设输入数据服从均匀分布，将数据分到有限数量的桶内，每个桶再分别排序（再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

　　计数排序本质上是一种特殊的桶排序，当桶的个数取最大(Vmax-Vmin+1)时，就变成了计数排序。

　　桶排序的时间复杂度（平均）是O(n+k)、空间复杂度是O(n+k)，为稳定性排序算法。

　　桶排序的算法步骤如下：

　　(1)设置一个定量的数组当作空桶。

　　(2)遍历输人数据，并且把数据一个个放到对应的桶内。

　　(3)对每个不是空的桶进行排序。

　　(4)从不是空的桶内把排好序的数据拼接起来。

　　比如：待排序数组arr=[31,25,43,9,27,18,5,44,38,26,17,34,1,8,48.13,79,7]根据数据的分布情况设置桶边界，bucket=[10,20,30,40,50]，用桶排序算法对这个数组进行排序的图解分析如下图所示。　　

　　程序代码：

　　运行结果：

　　练习题２：下面是一批学生的姓名、学号和数学成绩，请用桶排序法排序（一个桶装１个分数），使高分在前，低分在后；同分学号小的在前，学号大的在后。

姓名　　　学号　　　分数

李大伟　　２３　　　９０，

黄晨希　　１５　　　８８，

张丹丹　　１１　　　９０，

王丽丽　　２１　　　９５，

刘华旭　　１２　　　８８，

李小明　　　９　　　９４，

霍顺高　　　５　　　９７，

张飞鹏　　１０　　　８８，

李华峰　　　３　　　９９，

史大维　　　８　　　９０，

黄芬诗　　　２　　　９７。

　　基数排序

　　我们知道，一个2位自然数一定比一个1位自然数大，同理，n+1位自然数比n位自然数大，因此可以把数进行按位分级。对于十进制数，只有0到9十个数字，因此可以只用0到9十个桶进行同一级的划分，比它少位的和当前位是0的全部在0桶。可以想象，一位的自然数在第一次分桶（个位）后，就排好序了；然后第二次分桶（十位），由于一位的自然数十位是没有的，也就是0桶，那么一位的自然数顺次放入0桶还是保持原来的先后顺序；如此类推，直到最高位数的数被分桶。这种方法就是基数排序了。

　　基数排序也可称为按数位进行的分配排序（不是基于比较而是基于数据分配的）。其逻辑算法：列表中所有数按位上数值大小分配到对应的桶内，再将桶内的数按桶下标顺序放回到列表，列表中最大数值有几位数，这一来回就倒放几次，通过桶与列表的倒换完成排序。这种排序方式是目前稳定排序算法中效率最高的排序方式。

　　计数排序、桶排序、基数排序三者区别如下：

　　(1)基数排序和计数排序都可以看作桶排序。

　　(2)计数排序是一个桶装一个数（或相同的一组数），数越多，桶越多。

　　(3)桶排序是一个桶装一组数。

　　(4)基数排序是一个桶装一组数，然后倒回到数组中，再装一轮，再倒回去，按位摆桶。

　　n是数据个数，k是数据的位数，基数排序的时间复杂度（平均）是O(n×k)、空间复杂度是O(n+k)，为稳定性排序算法。比如：arr=[12,3,45,3543,214,10,121,4553,1,99,1008]，用基数排序算法对这个数组进行排序的图解分析如下图所示。

　　因数组中数字最长为4位，所以需4轮把数组全部排序完成。基数排序中没有任何比较操作，全凭分配倒放完成，因此拥有极高的排序效率。

　　程序代码：

　　运行结果：

　　初看起来，基数排序的执行效率似乎好得让人无法相信，所要做的只是把原始数据项从数组复制到桶数组，然后再复制回去。如果有10个数据项，则有20次复制，对每一位数据项重复一次这个过程。假设数组中最高有5位数，就需要20×5=100次复制。如果有100个数据项，那么就有200×5=1000次复制。复制的次数与数据项的个数成正比，即O(n)。这是一般被认为效率最高的排序算法。

　　不幸的是，假设数据项是不重复的，那么数据项越多，数据的位数就越长。例如，100个不同的数据项，就至少要2位数，1000个就三位，因此可以认为复制次数不是与数据项数无关，而是对数关系，即lgn。因此在大多数情况下，基数排序的执行效率倒退为O(nIgn)，比快速排序好一些（lgn<log2n），但差不多。

　　练习题３：十进制数需要十个桶，那么十六进制就需要十六个桶，修改程序使它适合各种进制的基数排序，并测试二和十六进制。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社