排序算法（3）- 桶排序、计数排序、基数排序

桶排序（Bucket sort）

将要排序的数据分到几个有序的桶里，每个桶里面再单独进行排序，最后把每个桶里的数据依次取出来，组成的序列就是有序序列。

看问题

对一组金额在0-50之间的订单进行排序：22,5,11,41,45,26,29,10,7,8,30,27,42,43,40

我们按0-9，10-19，20-29，30-39，40-49分5个桶，这样每个桶的数据就是[5,7,8]，[10,11]，[22,26,27,29]，[30]，[40,41,42,43,45]

分别对桶内数据排序，再取出即可。

如果要排序的数据有n个，把它们均匀地划分到m个桶内，每个桶里有k=n/m个元素，每个桶内部使用快速排序，时间复杂度为o(klogk)。m个桶排序复杂度就是O(mklogk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(nlog(n/m))。当桶的个数接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序时间复杂度接近O(n)。

计数排序（Counting sort）

如果排序的数据范围不大的话，例如查询高考分数，分数只可能是0_{780分，或者查询年龄1}120岁这样的话，那么就可以分成781个桶或者120个桶，只需要扫描遍历即可，所以时间复杂度是O(n)。

关键点在于"计数"

假设有8个考生，分数范围在0~5分之间，分别是：2，5，3，0，2，3，0，3，放在数组A[8]中

A[8]	2	5	3	0	2	3	0	3

以考生成绩作为下标，就能得到一个C[6]的桶，我们用这个桶来存储对应分数的考生个数，得到如下的数据：

C[6]	2	0	2	3	0	1
下标	0	1	2	3	4	5

这时对数组顺序求和：

C[6]	2	2	4	7	7	8
下标	0	1	2	3	4	5

接下来是怎么计算出每个考生在有序数组中对应的位置

我们从后到前一次扫描A[8]，当扫描倒数第一个3时，查找数组C中下标3对应的数字是7，说明分数小于等于3的考生个数是7，当前数字3就是7个考生里面的最后一个，那就可以把3放进数组R[8]的对应下标6的位置。

R[8]							3
下标	0	1	2	3	4	5	6	7

同时，C[6]中3对应的个数-1

C[6]	2	2	4	6	7	8
下标	0	1	2	3	4	5

加下来是0，对应的是2，则在R[8]中下标为1

R[8]		0					3
下标	0	1	2	3	4	5	6	7

c[0] = c[0] - 1

C[6]	1	2	4	6	7	8
下标	0	1	2	3	4	5

按这样的规律最后数组R内的数据就是从小到达有序排列。

下面是代码描述

def counting_sort(array):
    n = len(array)
    if n <= 1:
        return
    
    max = array[0]
    for item in array:
        if max < item:
            max = item
    
    countArray = []
    for i in range(0, max+1):
        countArray.append(0)

    # 计算每个元素的个数，放入C中
    for i in array:
        countArray[i] += 1

    count = len(countArray)

    # 依次累加    
    for i in range(1, count):
        countArray[i] = countArray[i-1] + countArray[i]
    
    resultArray = [0] * n
    for i in range(n-1, -1, -1):
        index = array[i]
        count = countArray[index]
        resultArray[count-1] = index
        countArray[index] = count-1

    for i in range(0, n):
        array[i] = resultArray[i]


if __name__ == "__main__":
    arr = [2, 5, 3, 0, 2, 3, 0, 3]
    counting_sort(arr)
    print(arr)

总结一下，在数据范围不大的场景中，可以使用计数排序，而且计数排序只能给非负整数排序，如果存在负数或小数情况，可以考虑手动调整到正整数范围内。

基数排序（Radix sort)

看问题

假设有10万个手机号码，怎么比较快速的从小到达排序？

用快排可以做到O(nlogn)，用上面的桶排序和计数排序范围太大了不适合，这时候就要用到基数排序。

手机号码有11位，a、b两个手机号，如果a的第一位就比b大，那后面就不用比较了。
我们先按照最后一位来排序手机号码，然后再按倒数第二位排序，以此类推，经过11次排序后，手机号码就都有序了。

根据每一位来排序，用桶排序或者计数排序，时间复杂度可以做到O(n)，如果要排序的数据有k位，总的时间复杂度是O(kn)，当k不大的时候，近似于O(n)。

如果排序的数据位数不是等长的，可以先把他们补齐，再排序。

总结基数排序就是可以把数据按位来比较，且每一位是递进关系。此外每一位的范围不能太大。

来自 https://leejnull.github.io/2020/03/02/2020-03-02-01/