桶排序算法 _桶排序

桶排序算法就是把数据平分到每一个桶中，然后对桶中的数据进行排序，再按桶的顺序依次倒出数据，桶排序算法很好理解。桶排序算法也是以空间换时间的算法。
举例说明一下桶排序算法的
以数组a = [61, 71, 14, 30, 18 ]为例，

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

以Python实现的桶排序算法：

def bucket_sort(elements, num):n = int(len(elements) / num) + 1buckets = [[] for i in range(n)]ma = max(elements)mi = min(elements)gap = int((ma - mi) / n) + 1for 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技术漫漫谈