桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort) 的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

1. 算法描述

• 设置一个定量的数组当作空桶；

• 遍历输入数据，并且把数据一个一个放到对应的桶里去；

• 对每个不是空的桶进行排序；

• 从不是空的桶里把排好序的数据拼接起来。

2. 图片演示

参考资料

3. 代码实现

def setData(pattern, num):
    datalist = []
    print('请输入数据'. format(num))

    for var in range(0, num):
        tmp = input('>>> ')
        while ((pattern-1) < int(tmp)) or (0 > int(tmp)):
            print('错误:数字超过了范围')
            tmp = input('>>> ')
        datalist.append(tmp)

    return datalist

def bucketSort(pattern, data, num):
    results = list()
    buckets = [[] for x in range(pattern)]
    print('INPUT: {}'. format(data))

    for x in range(0, num):
        buckets[ int(data[x]) ].append(data[x])

    i=0
    for x in range(0, pattern):
        y = 0
        maxlen = len(buckets[x])
        if maxlen is not 0:
            while y < maxlen:
                results.append(buckets[x][y])
                y += 1

    return results

def main():
    pattern = 10 # 0-9
    data = []
    result = []

    print('进行几项数据?')
    dataNum = input('>>> ')
    data = setData(pattern, int(dataNum))

    result = bucketSort(pattern, data, int(dataNum))
    print('RESULT: {}'. format(result))

if __name__ == '__main__':
    main()

4. 算法分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。