桶排序算法就是把数据平分到每一个桶中，然后对桶中的数据进行排序，再按桶的顺序依次倒出数据，桶排序算法很好理解。桶排序算法也是以空间换时间的算法。
举例说明一下桶排序算法的
以数组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。
以实现的桶排序算法：
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].end(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技术漫漫谈
胜象大百科
