计数排序、桶排序

计数排序适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。

计数排序原理：
找到给定序列的最小值与最大值
创建一个长度为最大值-最小值+1的数组，初始化都为0
然后遍历原序列，并为数组中索引为当前值－最小值的值＋１
此时数组中已经记录好每个值的数量，自然也就是有序的了

def count_sort(s):
    """计数排序"""
    # 找到最大最小值
    min_num = min(s)
    max_num = max(s)
    # 计数列表
    count_list = [0]*(max_num-min_num+1)
    # 计数
    for i in s:
        count_list[i-min_num] += 1
    s.clear()
    # 填回
    for ind,i in enumerate(count_list):
        while i != 0:
            s.append(ind+min_num)
            i -= 1

if __name__ == '__main__':
    a = [3,6,8,4,2,6,7,3]
    count_sort(a)
    print(a)

桶排序：适用于非整数
桶排序相当于把计数数组划分为按顺序的几个部分
每一部分叫做一个桶，它来存放处于该范围内的数
然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序
最后整个桶数组就是排列好的数据，再将其返回给原序列

def bucket_sort(s):
    """桶排序"""
    min_num = min(s)
    max_num = max(s)
    # 桶的大小
    bucket_range = (max_num-min_num) / len(s)
    # 桶数组
    count_list = [ [] for i in range(len(s) + 1)]
    # 向桶数组填数
    for i in s:
        count_list[int((i-min_num)//bucket_range)].append(i)
    s.clear()
    # 回填，这里桶内部排序直接调用了sorted
    for i in count_list:
        for j in sorted(i):
            s.append(j)

if __name__ == '__main__':
    a = [3.2,6,8,4,2,6,7,3]
    bucket_sort(a) 
    print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]