桶排序算法

桶排序算法就是把数据平分到每一个桶中，然后对桶中的数据进行排序，再按桶的顺序依次倒出数据，桶排序算法很好理解。桶排序算法也是以空间换时间的算法。

举例说明一下桶排序算法的

以数组a = [61, 71, 14, 30, 18 ]为例，

1. 假如每个桶放2个数，那就需要三个桶。
2. 找出数组中的最大值71，最小值14， 然后依次计算每个数据应该放入的桶。计算桶的最小间隔gap = (71-14)/3=19。
3. 每一个数据在桶中的位置 d = (a[i]- 14)/19。
4. 计算三个桶分别装的数据为[14, 18, 30], [], [61, 71]。
5. 把三个桶的数据收集起来，得到排序结果：14, 18, 30, 61, 71。

以Python/ target=_blank class=infotextkey>Python实现的桶排序算法：

def bucket_sort(elements, num):
    n = int(len(elements) / num) + 1
    buckets = [[] for i in range(n)]
    ma = max(elements)
    mi = min(elements)
    gap = int((ma - mi) / n) + 1
    for e in elements:
        d = int(((e - mi) / gap))

        bucket_size = len(buckets[d])
        for b in range(bucket_size):
            if e < buckets[d][b]:
                buckets[d].insert(b, e)

        if bucket_size == len(buckets[d]):
            buckets[d].Append(e)
    
    del elements[:]
    for bucket in buckets:
        for b in bucket:
            elements.append(b)

if __name__ == '__main__':
    arr = [61, 71, 14, 30, 18]
    bucket_sort(arr, 2)
    print(arr)

运行结果为：

[14, 18, 30, 61, 71]

更多内容请关注微信公众号：IT技术漫漫谈