计数排序、基数排序、桶排序则属于非比较排序，算法时间复杂度O(n)，优于比较排序。但是也有弊端，会多占用一些空间，相当于是用空间换时间。

1. 计数排序：

计数排序的基本思想是：对每一个输入的元素a[i]，确定小于 a[i] 的元素个数。所以可以直接把 a[i] 放到它输出数组中的位置上。假设有5个数小于 a[i]，所以 a[i] 应该放在数组的第6个位置上。

实现代码如下：

def counting_sort(a, k):  # k = max(a)
    n = len(a)  # 计算a序列的长度
    b = [0 for i in range(n)]  # 设置输出序列并初始化为0
    c = [0 for i in range(k + 1)]  # 设置计数序列并初始化为0，
    for j in a:
        c[j] = c[j] + 1
    for i in range(1, len(c)):
        c[i] = c[i] + c[i-1]
    for j in a:
        b[c[j] - 1] = j
        c[j] = c[j] - 1
    return b

2. 桶排序：

桶排序的基本思想是：把数组a划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。桶排序要求数据的分布必须均匀，不然可能会失效。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。


def bucket_sort(a):
    buckets = [0] * ((max(a) - min(a)) + 1)  # 初始化桶元素为0
    for i in range(len(a)):
        buckets[a[i] - min(a)] += 1  # 遍历数组a，在桶的相应位置累加值
    b = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            b += [i + min(a)] * buckets[i]
    return b

算法实现步骤

根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
遍历排序序列，将每个元素放到对应的桶里去；
对不是空的桶进行排序；
按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置，完成排序。实现代码如下：

def Bucket_Sort(array, bucketsize):
        #bucket_size: 桶大小
    minValue = min(array)
    maxValue = max(array)
    res = []
    bucketcount = (maxValue - minValue + 1) // bucketsize  #确定桶个数
    bucket_lists = [[] for i in range(bucketcount)]

    for i in array:
        bucket_index = (i - minValue) // bucketsize
        bucket_lists[bucket_index].append(i)
    # 桶内排序
    for j in bucket_lists:
        Quick_Sort_2(j, 0, len(j)-1)    

    for j in bucket_lists:
        if len(j) != 0:
            res.extend(j)
    return res