桶排序思想下的排序

• 计数排序
• 基数排序

分析：

• 桶排序思想下的排序都是不基于比较的排序
• 时间复杂度为O(N)，额外空间复杂度O(N)
• 应用范围有限，需要样本的数据状态满足桶的划分

计数排序

举个例子

假设现在有一个数组，统计了人的年龄，也就是说里面的数值范围是0～200（人的寿命范围假设为0～200），并且都是整数，此时如果我们需要对其年龄进行排序。

思路

• 首先得到词频数组：申请一个长度为200的数组arr，每遍历到一个年龄，就在arr的相应index的值加1（比如统计数据是三个人，有一个人年龄是1岁，两个人是3岁，那么arr就是[0,1,0,2]，index对应年龄，值代表该年龄的人的数量）
• 将词频数组进行转换还原：还原规则是，遍历词频数组，遇到值小于0时，不做任何操作，当值大于0时，已经知晓当前index和value，也就是年龄，以及处于该年龄的数量，在res数组中pushvalue个index，那么还原后的数组就是[1,3,3]

复杂度

在上述过程中，遍历数组所需的时间复杂度就是O(N)

适用范围

假设上面的例子中，数组不是整数，数值范围也没有进行限制，比如数值是一个很大的复数，并且是一个根号值，在这种情况下，我们也不可能会去申请一个长度巨大的数组。

因此，计数排序是基于数据状况做的排序，相对于基于比较的排序，使用范围很窄。

基数排序

算法思想：基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

具体步骤

假设现在有数组[17,13,25,100,72]需要排序。

• 1.确定最大位数为3，补齐位数的数组就是[017,013,025,100,072]
• 2.申请桶（也可称之为容器，归根结底是一个数组或队列），假设分别为arr0、arr1、arr2...
• 3.按个位数，将元素放入桶内，arr0=[100]，arr1=[]，arr2=[072]，arr3=[013]，arr4=[]，arr5=[025]，arr6=[]，arr7=[017]。再按桶顺序将元素倒出，得到[100,072,013,025,017]
• 4.按十位数，将元素放入桶内，arr0=[100]，arr1=[013，017]，arr2=[025]，arr3=[]，arr4=[]，arr5=[]，arr6=[]，arr7=[072]。再按桶顺序将元素倒出，得到[100,013,017,025,072]
• 5.按百位数，将元素放入桶内，arr0=[013,017,025,072]，arr1=[100]，arr2=[]，arr3=[]，arr4=[]，arr5=[]，arr6=[]，arr7=[]。再按桶顺序将元素倒出，得到[013,017,025,072,100]，此时就排好序了

图例分析

待排序序列为：[53, 3, 542, 748, 14, 214, 154, 63, 616]，数位长度为3。

适用范围

可以看到，基数排序是依靠位数来进行排序，也就是说要求排序的对象需要有进制。所以基数排序也是不基于比较，而是基于数据状况的排序。

基数排序也是基于数据状况做的排序，但是比计数排序更好（基数排序是，几个进制就几个桶）