计数排序

计数排序是已知列表元素的范围，统计列表元素出现的频次，再进行排序，例如：

li=[2,5,2,7,7,7,8]

在上面的列表中，元素2出现了两次，5出现了一次，7出现了三次，8出现了一次，再通过元素出现的次数来输出列表，示例代码如下：

def count_sort(li,max_count):
    print('排序前：',li)
    count=[0 for _ in range(max_count+1)]       # 长度为max_count，值全为0的列表
    for val in li:                              # 遍历列表的值
        count[val]+=1                           # 计数
    li.clear()                                  # 清空列表
    print('统计列表元素出现的次数',count)           # 输出count列表
    for index,val in enumerate(count):          # 遍历列表的
        for i in range(val):                    # 根据count列表的值来遍历几次
            li.append(index)                    # 添加元素

li=[3,5,2,5,1,1,6,10,9,8]
count_sort(li,10)
print('排序后',li)

运行结果如下图所示：

因为列表的下标是从0开始的，所以统计列表元素出现的次数为0出现了0次，1出现了2次，2出现了一次，3出现了1次等等。

计数排序的缺点：

消耗大量内存；
需要知道要排序的列表最大值；

桶排序

桶排序算是计数排序的升级版，桶排序首先把元素分在不同的桶中，再对每个桶中元素排序。如下图所示：

其实每个桶表示一个空列表，示例代码如下：

def bucket_sort(li, n=4, max_num=40):
    buckets = [[] for _ in range(n)]           # 创建桶
    for var in li:
        i = min(var // (max_num // n), n - 1)  # i 表示元素放在哪个桶
        buckets[i].append(var)                 # 把元素放在桶里
        # 桶内排序
        for j in range(len(buckets[i]) - 1, 0, -1):     # 从桶的后面往前面比较元素大小
            if buckets[i][j] < buckets[i][j - 1]:
                buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
            else:
                break
    sorted_li = []                          
    for buc in buckets:             
        sorted_li.extend(buc)                   # 合并桶
    return sorted_li

li=[35,22,12,19,20,5,10,15]
print(bucket_sort(li))

运行结果如下：

基数排序

基数排序是根据元素位数进行排序，例如，先按照元素的个位数来排序，按照元素的十位数来排序，再按照百位、千位等等。如下图所示：

示例代码如下：

def radix_sort(li):
    max_num = max(li)  # 获取列表最大值
    it = 0
    # 根据最大值来判断进行元素的个位、百位、千位、万位来排序
    while 10 ** it <= max_num:
        buckets=[[] for _ in range(10)]     # 创建空列表
        for var in li:
            digit=(var//10**it)%10
            buckets[digit].append(var)      # 插入空列表中
        li.clear()
        for buc in buckets:
            li.extend(buc)          # 合并
        it += 1
        print(li)
li=[22,54,28,32,14,33,56,12]
radix_sort(li)

运行结果如下：