桶排序

题目描述
给定一个包含 n 个元素的浮点数数组 arr，其中每个元素的范围在 [0, 1) 内（即 0 ≤ arr[i] < 1）。请设计一个排序算法，将数组按升序排列。要求时间复杂度接近 O(n)，且不能直接使用内置排序函数。

解题过程

步骤 1：理解桶排序的核心思想
桶排序适用于数据均匀分布在某个范围内的情况。它的基本思路是：

1. 将区间划分为若干个桶（bucket）。
2. 将元素分配到对应的桶中。
3. 对每个桶内的元素进行排序（可使用简单排序算法）。
4. 按桶的顺序依次输出所有元素。

对于本题，数据范围是 [0, 1)，可以将其均匀划分为 n 个桶（每个桶的区间大小相等）。

步骤 2：设计桶的分配规则
假设我们创建 n 个桶，编号为 0 到 n-1。
对于任意元素 arr[i]，它应该放入的桶索引为：

index = floor(arr[i] * n)

例如：

• 若 n = 10，arr[i] = 0.78，则 index = floor(0.78 * 10) = 7。
• 若 arr[i] = 0.0，则 index = 0；若 arr[i] ≈ 0.999，则 index = n-1。

这样，每个桶的区间为：

• 桶 0：[0, 1/n)
• 桶 1：[1/n, 2/n)
• ...
• 桶 n-1：[(n-1)/n, 1)

步骤 3：分配元素到桶中
遍历数组，将每个元素放入对应的桶。桶可以用链表或动态数组实现。
例如：

arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
n = 7
桶索引计算：
0.42 * 7 = 2.94 → 桶 2
0.32 * 7 = 2.24 → 桶 2
0.33 * 7 = 2.31 → 桶 2
0.52 * 7 = 3.64 → 桶 3
0.37 * 7 = 2.59 → 桶 2
0.47 * 7 = 3.29 → 桶 3
0.51 * 7 = 3.57 → 桶 3

分配后：

• 桶 2: [0.42, 0.32, 0.33, 0.37]
• 桶 3: [0.52, 0.47, 0.51]
• 其余桶为空

步骤 4：对每个桶内部排序
由于数据是均匀分布的，每个桶内的元素数量会很少（平均每个桶约 1 个元素）。
可以使用插入排序等简单算法对每个非空桶排序。
例如对桶 2 排序后：

桶 2: [0.32, 0.33, 0.37, 0.42]
桶 3: [0.47, 0.51, 0.52]

步骤 5：按顺序合并桶
从桶 0 到桶 n-1，依次输出每个桶内的元素，即可得到有序数组。
结果：

[0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

步骤 6：复杂度分析

• 分配阶段：O(n)
• 桶内排序：若数据均匀分布，每个桶内元素数量接近常数，则排序总时间为 O(n)
• 最坏情况（所有元素挤在一个桶内）：退化为 O(n²)
• 空间复杂度：O(n)（用于存储桶）

总结
桶排序在数据均匀分布时效率极高，本题通过将 [0, 1) 区间划分为 n 个桶，确保了平均情况下的线性时间复杂度。关键在于合理划分桶和选择桶内排序算法。