35 lines
1.3 KiB
Python
35 lines
1.3 KiB
Python
|
"""
|
|||
|
|
桶排序：通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；
|
|||
|
|
最终按照桶的顺序将所有数据合并。
|
|||
|
|
|
|||
|
|
前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。
|
|||
|
|
此类排序算法的时间复杂度无法超越 O(nlog2n)
|
|||
|
|
|
|||
|
|
考虑一个长度为 n 的数组，其元素是范围 [0, 1) 内的浮点数:
|
|||
|
|
|
|||
|
|
1. 初始化 k个桶，将 n 个元素分配到 k 个桶中。
|
|||
|
|
2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
|
|||
|
|
3. 按照桶从小到大的顺序合并结果。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
def bucket_sort(nums: list[int]):
|
|||
|
|
# 初始化 k = n / 2 个桶，预期向每个桶分配2个元素
|
|||
|
|
k = len(nums) // 2
|
|||
|
|
buckets = [[] for _ in range(k)]
|
|||
|
|
|
|||
|
|
# 1. 将数组元素分配到对应的桶中
|
|||
|
|
for num in nums:
|
|||
|
|
# 输入数据范围为 [0, 1)，所以使用 num*k 可将 num*k 映射到范围[0, k-1]
|
|||
|
|
i = int(num * k)
|
|||
|
|
buckets[i].append(num)
|
|||
|
|
|
|||
|
|
for bucket in buckets:
|
|||
|
|
# 对各个桶内的数排序
|
|||
|
|
bucket.sort()
|
|||
|
|
|
|||
|
|
i = 0
|
|||
|
|
for bucket in buckets:
|
|||
|
|
for num in bucket:
|
|||
|
|
nums[i] = num
|
|||
|
|
i += 1
|