计数排序、桶排序、基数排序：辨析理解、javascript实现代码、C#实现代码

╰半夏微凉° 2022-05-16 08:42 99阅读 0赞

计数排序、桶排序、基数排序都是基本排序算法，网上有很多关于他们的思想原理和实现代码。但是，很多博客在讲述它们时并没有阐述得很清除，有些还混淆了它们三者的概念：有些人认为计数排序是桶排序，有些人认为桶排序是基数排序等等。

先来看看它们各自的基本思想和算法步骤：

## 计数排序 Counting Sort ##

**基本思想：**  
　　Out-place（外部排序）、计数排序、非比较的排序算法。  
　　计数排序对一定量的整数排序的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序。  
　　对于一个输入数组中的一个元素i，只要我们知道了这个数组中比i小的元素的个数x，那么我们就可以直接把i放到第（x+1）个位置，即i的索引为x（索引从0开始）。

**算法步骤：**  
　　1) 找出数组中的最大值和最小值;  
　　2) 统计数组中每个值i的元素出现的次数，将其存入新数组的第i项；  
　　3) 从最小值开始依次计算小于该元素的元素个数x，则该元素在有序数组中的索引值为x  
或者：  
　　1) 找出数组中的最大值和最小值;  
　　2) 统计数组中每个值i的元素出现的次数，将其存入新数组的第i项；  
　　3) 将上面的数组根据索引i的值依次在新数组中展开索引i，其结果则为有序数组。

**时间复杂度：**  
　　最佳情况：T(n) = O(n+k)；  
　　最差情况：T(n) = O(n+k)；  
　　平均情况：T(n) = O(n+k)；  
　　稳定性：稳定；  
　　空间复杂度：O(k)。

## 桶排序 Bucket Sort ##

**基本思想：**  
　　Out-place（外部排序）、非比较的排序算法。  
　　桶排序是计数排序的升级版。它利用了函数的映射关系（比较规则），高效与否的关键就在于这个映射函数的确定（计数排序可以看做函数映射关系为f(x)=x或f(x)=x-min）。  
　　假设输入由一个随机过程产生，该过程将元素一致地分布在区间\[0，1)上。桶排序的思想就是把区间\[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在\[0，1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

**算法步骤：**  
　　1) 建立一个函数的映射关系f(x)=ax+b等；  
　　2) 根据映射关系建立多个桶f(x)；  
　　3) 依次将数据放入对应桶中；  
　　4) 对桶内数据进行排序，可以继续使用桶排序，也可以使用其他排序；  
　　5) 依次输出各个桶内数据，即为有序序列。

**时间复杂度：**  
　　最佳情况：T(n) = O(n+k)；  
　　最差情况：T(n) = O(![n^\{2\}][n_2])；  
　　平均情况：T(n) = O(n+k)；  
　　稳定性：稳定(但若桶内排序不稳定则整体不稳定)；  
　　空间复杂度：O(n+k)。

## 基数排序 Radix Sort ##

**基本思想：**  
　　Out-place（外部排序）、桶排序、非比较的排序算法、分配式排序。  
　　基数即指位数，基数排序即位数排序。  
　　基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

**算法步骤：**  
　　1) 根据最低位/最高位，建立规则创建多个桶，并为桶编好序号;  
　　2) 根据最低位/最高位，按规则将各个数据放入对应的桶中；  
　　3) 根据序号依次将桶内数据放回数组中；  
　　4) 根据上一位/下一位，建立新的规则重复上述步骤直到序列有序。  
例如，对数字进行排序（不含负数，如果是负数还要判定负号）：  
　　1) 创建10个桶，根据个位数依次放入对应的桶中;  
　　2) 根据序号依次将桶内数据放回数组中；  
　　3) 根据十位数、百位数等重复上述步骤，最后一次放回数组时序列有序。  
例如，对相同固定长度的字符串进行排序（只考虑全小写）：  
　　1) 根据26个字母创建26个桶，根据最后一个字母依次放入对应的桶中;  
　　2) 根据序号依次将桶内数据放回数组中；  
　　3) 根据倒数第二位字母、倒数第三位字母等重复上述步骤，最后一次放回数组时序列有序。

以上的两个例子都是从低位优先（最低位优先(Least Significant Digit first, LSD)法），也可以高位优先（最高位优先(Most Significant Digit first, LSD)法）。

**时间复杂度：**  
　　最佳情况：T(n) = O(d(n+r))；  
　　最差情况：T(n) = O(d(n+r))；  
　　平均情况：T(n) = O(d(n+r))；  
　　稳定性：稳定；  
　　空间复杂度：O(n+r)。

## 辨析 ##

其实，从它们的基本思想就可以看出来三者的区别：

**计数排序**就是计算比某个数小的元素总数的个数，因此总数个数加1就是该数的位置，当某数多次重复时要复杂一点。其实计数排序和桶排序在思想上没有关系，有关系的是实现过程，而且这个关系并不是必须的。  
　　在计数排序，思想中心是求出比某个数小的元素总数的个数，那么，怎么求这个总数个数呢？有多种方法，其中一种就是利用桶排序，根据数组最大值建立桶的个数和新数组，桶的序号即新数组的索引，它包含了原数组中所有元素的值，因此只要值出现一次，新数组索引对应的值就从0开始依次递增，这样就可以求出原数组每个值出现的次数，且由于索引是递增的，因此值是按递增排列的，具体看上面计数排序中利用桶排序的思想进行排序的步骤，以及计数排序里的代码示例。  
　　**桶排序**是对所有数据进行分析并建立一定的函数关系（规则），然后根据该规则将数据放入对应桶中，再对每个桶内数据进行排序。  
　　因此，计数排序中的桶排序起到的作用是使元素值按顺序排列，因为桶序号代表元素值，而由于桶序号的唯一性和规则性，每个元素值只出现一次，且这个排列的顺序中不仅包含所有元素值，还有其他无关的值，而桶内元素代表无序序列相同值出现的次数。而对于桶排序，桶序号是与元素值有关的映射关系（其实计数排序也是与元素值有关的映射关系，如桶序号等于元素值，则映射关系为f(x)=x），桶内元素就是无序序列的元素值。  
　　**基数排序**的思想是按位数排列，不论是最高位优先法MSD，还是最低位优先法LSD，它的中心都是依次对数据的同一位进行规则建立，分配入桶，然后依次取出，当最后一位按规则入桶然后依次取出后，必然为有序数列。  
　　因此从上面分析来看，计数排序只是在实现其中心思想上使用了桶排序的方法，借用桶排序这种手段来实现计数排序的计数；桶排序是按一定规则对数据进行分类然后合并，可以说是一种分治法；而基数排序是建立在桶排序之上的，它的核心是对每一位（即基数）进行桶排序。

github链接：**[javascript与C\#实现基本排序算法、搜索算法 algorithm-sort\_search][javascript_C_ algorithm-sort_search]**

[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D
[javascript_C_ algorithm-sort_search]: https://github.com/Epulari/algorithm-sort_search