桶排序(最快最简单的排序)
程序员文章站
2022-05-13 21:37:42
...
第十一章 23
// An highlighted block
def bucketSort(nums):
max_num = max(nums)
# 创建一个元素全是 0 的列表, 当做桶
bucket = [0]*(max_num+1)
print(bucket)
# 把所有元素放入桶中, 即把对应元素个数加一
for i in nums:
bucket[i]+=1
# 存储排序好的元素
sort_nums = []
# 取出桶中的元素
for j in range(len(bucket)):
if bucket[j]!=0:
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
nums = [5,6,3,2,1]
print(bucketSort(nums))
桶排序的基本思想是将一个数据表分割成许多 buckets,然后每个 bucket 各自排序,或用不同的排序算法,或者递归的使用 bucket sort 算法。也是典型的 divide-and-conquer 分而治之的策略。它是一个分布式的排序,介于 MSD 基数排序和 LSD 基数排序之间。
1、桶排序是稳定的
2、桶排序是常见排序里最快的一种, 大多数情况下比快排还要快
3、桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
下一篇: 机器人时代 激光技术扮演什么角色