桶排序算法就是把數(shù)據(jù)平分到每一個(gè)桶中，然后對(duì)桶中的數(shù)據(jù)進(jìn)行排序，再按桶的順序依次倒出數(shù)據(jù)，桶排序算法很好理解。桶排序算法也是以空間換時(shí)間的算法。
舉例說(shuō)明一下桶排序算法的
以數(shù)組a = [61, 71, 14, 30, 18 ]為例，
- 假如每個(gè)桶放2個(gè)數(shù)，那就需要三個(gè)桶。
- 找出數(shù)組中的最大值71，最小值14， 然后依次計(jì)算每個(gè)數(shù)據(jù)應(yīng)該放入的桶。計(jì)算桶的最小間隔gap = (71-14)/3=19。
- 每一個(gè)數(shù)據(jù)在桶中的位置 d = (a[i]- 14)/19。
- 計(jì)算三個(gè)桶分別裝的數(shù)據(jù)為[14, 18, 30], [], [61, 71]。
- 把三個(gè)桶的數(shù)據(jù)收集起來(lái)，得到排序結(jié)果：14, 18, 30, 61, 71。
以Python實(shí)現(xiàn)的桶排序算法：
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)
運(yùn)行結(jié)果為：
[14, 18, 30, 61, 71]
更多內(nèi)容請(qǐng)關(guān)注微信公眾號(hào)：IT技術(shù)漫漫談
