桶排序算法演示 - NOI提高级教程

📖 算法原理：区间映射与桶内局部排序

桶排序（Bucket Sort）是一种工作原理为将数组分发到有限数量的桶子里的分布类排序算法。每个桶再个别排序，最终依次收集拼接。

📐 桶排序分发、桶内排序与合并收集断言

其核心运行流程如下：

划分区间：依据元素分布范围，建立 $K$ 个空桶，每个桶代表一段连续的数值子区间（例如区间 $[0-9], [10-19], [20-29], \dots$）。
重力分发（Scatter）：扫描待排序数组，计算各元素 $arr[i]$ 应属于的桶索引 idx = arr[i] / bucket_range，并将其平滑丢入对应的桶中。时间复杂度为 $O(N)$。
桶内排序：对每个非空的桶，分别使用常规算法（如插入排序 Insertion Sort）进行桶内排序。
顺序收集（Gather）：按桶索引从小到大的顺序，依次从各桶底部取出已排好序的元素，组装写回原数组。

🚀 时空复杂度分析：在元素分布非常均匀（Uniform Distribution）的理想状态下，每个桶仅分得 $N/K$ 个元素。若桶内采用 $O(M \log M)$ 排序，总时间复杂度为 $O(N + K \cdot \frac{N}{K} \log \frac{N}{K})$。当 $K \approx N$ 时，时间复杂度逼近极限 $O(N)$！

输入 8 个元素 (范围 0-49)：

演示速度：

输入 0-49 范围内的整数（逗号隔开），点击“开始桶排序”观察下落动画。

🪣 雨点重力分发与桶内链条 (Scatter & Gather Playground)

[0-9]

[10-19]

[20-29]

[30-39]

[40-49]

收集区准备中

void bucketSort(int arr[], int n) {
    // 1. 创建 5 个子区间桶
    vector<int> buckets[5];
    
    // 2. 扫描数组分发入对应的桶中
    for (int i = 0; i < n; i++) {
        int idx = arr[i] / 10; // 计算桶索引
        buckets[idx].push_back(arr[i]);
    }
    
    // 3. 桶内排序并顺序收集写回
    int index = 0;
    for (int i = 0; i < 5; i++) {
        // 对非空桶执行插入排序
        sort(buckets[i].begin(), buckets[i].end()); 
        for (int x : buckets[i]) {
            arr[index++] = x; // 顺序写回
        }
    }
}

📋 桶排序执行步骤历史