桶排序（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）
如果排序的数据范围不大的话，例如查询高考分数，分数只可能是0780分，或者查询年龄1120岁这样的话，那么就可以分成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)。
如果排序的数据位数不是等长的，可以先把他们补齐，再排序。
总结基数排序就是可以把数据按位来比较，且每一位是递进关系。此外每一位的范围不能太大。
