Bucket Sort（桶排序）

1. 桶排序的基本思想

• 桶排序假设输入数组 $$A[1\dots n]$$ 的元素是 均匀分布在区间 [0,1) 上
• 核心思路：
  1. 将区间 $$[0,1)$$ 平均划分成 $$n$$ 个子区间（桶）
  2. 将每个元素 $$A[i]$$ 放入对应的桶：
     $$\text{桶索引}=\lfloor n\cdot A[i]\rfloor$$
  3. 对每个桶内的元素使用 插入排序 排序
  4. 按桶顺序依次输出所有元素，得到最终排序结果
• 由于输入均匀分布，每个桶内期望元素数目不多，因此平均情况下排序时间接近线性。

2. 桶排序伪代码

BUCKET-SORT(A, n)
1  let B[0..n-1] be a new array of empty lists
   // 创建一个长度为 n 的数组 B，每个位置都是一个空链表（桶）
   // B[i] 用来存放落在第 i 个区间的元素
2  for i = 1 to n
   // 遍历输入数组 A 的每一个元素
3      insert A[i] into list B[floor(n * A[i])]
   // 计算元素 A[i] 应该放入的桶
   // 公式为 floor(n * A[i])，将 [0,1) 区间均匀划分为 n 个桶
   // 将 A[i] 插入对应的桶中（桶可以使用链表或者动态数组）
4  for i = 0 to n-1
   // 遍历所有桶
5      sort list B[i] with insertion sort
   // 对每个桶内部的元素进行排序
   // 使用插入排序是因为每个桶元素数量较少，插入排序在小数据量时效率高
6  concatenate lists B[0], B[1], ..., B[n-1] in order
   // 按顺序将所有桶中的元素依次连接起来
   // 先输出 B[0] 的元素，再输出 B[1]，依次类推，得到完全排序后的数组
7  return concatenated list
   // 返回排序后的最终数组

3. 桶排序的正确性

• 对任意两个元素 $$A[i]\le A[j]$$：
  1. 如果它们在同一个桶内，插入排序保证顺序正确
  2. 如果它们在不同桶内，桶的顺序保证 $$A[i]$$ 出现在 $$A[j]$$ 之前
     因此，最终合并所有桶得到的数组是排序后的数组。

4. 桶排序时间复杂度分析

4.1 总时间公式

• 除了每个桶内排序，其余操作都是 $$O(n)$$
• 假设 $$n_i$$ 为桶 $$i$$ 中的元素数量
• 插入排序时间：
  $$O(n_i^2)$$
• 总时间：
  $$T(n)=O(n)+\sum _{i=0}^{n-1}O(n_i^2)$$

4.2 平均时间复杂度

• 假设输入均匀独立分布，每个桶的元素数量 $$n_i$$ 是随机变量
• 期望：
  $$E[n_i]=1$$
• 对平方的期望：
  $$E[n_i^2]=\text{Var}(n_i)+(E[n_i]{)}^2=(1-\frac{1}{n})+1=2-\frac{1}{n}$$
• 代入总时间公式：
  $$E[T(n)]=O(n)+\sum _{i=0}^{n-1}O(E[n_i^2])=O(n)+n\cdot O(2-\frac{1}{n})=O(n)$$
• 因此平均情况下，桶排序 时间复杂度为 $$O(n)$$

5. 总结

1. 假设：元素均匀分布在 $$[0,1)$$
2. 步骤：划桶 → 放入桶 → 桶内排序 → 合并
3. 正确性：同桶靠插入排序，不同桶按桶顺序
4. 时间复杂度：
   • 最坏情况：所有元素集中在同一个桶 → $$O(n^2)$$
   • 平均情况（均匀分布）：$$O(n)$$
5. 核心公式：
   $$\text{桶索引}=\lfloor n\cdot A[i]\rfloor ,T(n)=O(n)+\sum _{i=0}^{n-1}O(n_i^2),E[T(n)]=O(n)$$

#include <iostream>
#include <vector>
#include <list>
#include <algorithm> // 用于 std::sort 或者可以用插入排序自定义
using namespace std;
// 桶排序函数，假设数组元素在 [0,1) 之间
void bucketSort(vector<double>& A) {
    int n = A.size();
    // 1. 创建 n 个空桶
    vector<list<double>> B(n);
    // 2. 将每个元素放入对应的桶
    for (int i = 0; i < n; i++) {
        int index = int(n * A[i]); // 桶索引
        B[index].push_back(A[i]);
    }
    // 3. 对每个桶内元素进行排序（使用插入排序）
    for (int i = 0; i < n; i++) {
        B[i].sort(); // list 自带稳定排序
    }
    // 4. 将所有桶中的元素按顺序连接回数组 A
    int idx = 0;
    for (int i = 0; i < n; i++) {
        for (double val : B[i]) {
            A[idx++] = val;
        }
    }
}
int main() {
    vector<double> A = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
    cout << "原数组: ";
    for (double x : A) cout << x << " ";
    cout << endl;
    bucketSort(A);
    cout << "排序后: ";
    for (double x : A) cout << x << " ";
    cout << endl;
    return 0;
}

一个 Bucket Sort 的示例，并用表格展示每一步。数组为：

$$A=[0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68]$$
桶数量 $n=10$，每个桶存放区间为：
$$B[i]=[i/10,(i+1)/10)$$

1. 将元素放入对应桶

元素	桶索引	放入的桶
0.78	7	B[7]
0.17	1	B[1]
0.39	3	B[3]
0.26	2	B[2]
0.72	7	B[7]
0.94	9	B[9]
0.21	2	B[2]
0.12	1	B[1]
0.23	2	B[2]
0.68	6	B[6]

2. 每个桶内部排序（插入排序）

桶	排序后内容
B[0]	-
B[1]	0.12, 0.17
B[2]	0.21, 0.23, 0.26
B[3]	0.39
B[4]	-
B[5]	-
B[6]	0.68
B[7]	0.72, 0.78
B[8]	-
B[9]	0.94

3. 合并桶得到最终排序数组

$$A_{\text{sorted}}=[0.12,0.17,0.21,0.23,0.26,0.39,0.68,0.72,0.78,0.94]$$
这个示例清楚地展示了 Bucket Sort 的三个主要步骤：

1. 分桶
2. 桶内排序
3. 合并桶
   下面对 Chapter 8.4 的 Exercises 进行详细理解和数学公式表示。

8.4-1

任务：模拟 BUCKET-SORT 对数组
$$A=[0.79,0.13,0.16,0.64,0.39,0.20,0.89,0.53,0.71,0.42]$$
的排序过程。
分析：

• 桶数量 $n=10$，每个桶区间为：
  $$B[i]=[i/10,(i+1)/10),i=0,1,\dots ,9$$
• 将元素分配到对应桶：

  元素	桶索引	放入的桶
  0.79	7	B[7]
  0.13	1	B[1]
  0.16	1	B[1]
  0.64	6	B[6]
  0.39	3	B[3]
  0.20	2	B[2]
  0.89	8	B[8]
  0.53	5	B[5]
  0.71	7	B[7]
  0.42	4	B[4]

• 桶内排序（使用插入排序）：

  桶	排序后内容
  B[0]	-
  B[1]	0.13, 0.16
  B[2]	0.20
  B[3]	0.39
  B[4]	0.42
  B[5]	0.53
  B[6]	0.64
  B[7]	0.71, 0.79
  B[8]	0.89
  B[9]	-

• 合并桶得到最终排序数组：
  $$A_{\text{sorted}}=[0.13,0.16,0.20,0.39,0.42,0.53,0.64,0.71,0.79,0.89]$$

8.4-2

问题： 为什么最坏情况下 Bucket Sort 时间是
$$O(n^2)$$
原因：

• 如果所有元素落在同一个桶里，那么插入排序需要对 $n$ 个元素排序，时间为 $O(n^2)$。
  优化方案：
• 将桶内排序改用 比较类的排序算法（如快速排序或归并排序），时间复杂度 $O(n\log n)$，仍然保持平均线性时间。

8.4-3

随机变量 $X$：两次抛硬币正面数。

• 取值 $X\in 0,1,2$，概率分别为：
  $$P(X=0)=\frac{1}{4},P(X=1)=\frac{2}{4}=\frac{1}{2},P(X=2)=\frac{1}{4}$$
• 计算期望平方：
  $$E[X^2]=0^2\cdot \frac{1}{4}+1^2\cdot \frac{1}{2}+2^2\cdot \frac{1}{4}=0+\frac{1}{2}+1=\frac{3}{2}$$
• 计算平方期望：
  $$E[X]=0\cdot \frac{1}{4}+1\cdot \frac{1}{2}+2\cdot \frac{1}{4}=1⟹E[X{]}^2=1$$

8.4-4

数组 $A$ 的生成：
$$A[i]=\lfloor 10x_i\rfloor +y_i,x_i,y_i\sim \text{Uniform}(0,1)$$
修改 Bucket Sort 方法：

1. 按 $0\le A[i]<10$ 的整数部分分桶。
2. 桶内只包含少量元素，使用插入排序。
3. 由于整数部分 $0-9$ 均匀分布，期望时间仍然为 $O(n)$。

8.4-5

单位圆内 $n$ 个点 $(x_i,y_i)$，距离原点：
$$d_i=\sqrt{x_i^2+y_i^2}$$
思路：

• 均匀分布点在单位圆中，面积与半径平方成比例：
  $$P(d_i\le r)=r^2$$
• 将半径 $[0,1]$ 划分为 $n$ 个桶，每个桶半径间隔：
  $$\text{桶 }i:[\sqrt{i/n},\sqrt{(i+1)/n})$$
• 桶内使用插入排序，平均时间 $O(n)$。

8.4-6

给定可计算的连续分布函数 $P(x)$，$P(x)=\mathrm{Pr}(X\le x)$。
算法思路：

1. 将 $n$ 个随机变量 $X_i$ 映射到 $U_i=P(X_i)$，则 $U_i\sim \text{Uniform}(0,1)$。
2. 对 $U_i$ 使用 Bucket Sort 排序。
3. 输出对应的 $X_i$，时间期望 $O(n)$。