桶排序
一句话总结
桶排序通过「分配元素到桶 → 对每个桶排序 → 合并有序桶」三步骤实现排序，是归并排序与计数排序的通用形式。
核心要点
1. 桶排序三步骤
- 分配：将待排序数组中的元素使用映射函数分配到若干个「桶」中
- 排序：对每个桶中的元素进行排序（可使用任意排序算法）
- 合并：将这些排好序的桶按顺序合并，得到最终排序结果
2. 桶排序与归并排序的联系
桶排序的思路类似归并排序：都是把大的数组分成小的数组进行排序，最后再合并。但桶排序更加灵活：
- 归并排序是固定二分（k=2）
- 桶排序可灵活决定桶的数量 k 和映射函数
3. 桶排序与计数排序的联系
当桶的数量 k 无限大，每个桶至多只有一个元素时，桶排序就转化成了计数排序，复杂度降低到 O(n)。
关系总结：
桶排序 (通用形式)
├─ k=2 时 → 类似归并排序
└─ k 足够大时 → 计数排序
4. 分开排序更高效（数学证明）
以选择排序为例：直接对大小为 n 的数组排序，时间复杂度 O(n²)。
若将数组分成 k 个桶，每个桶大小为 n₁, n₂, ..., nₖ（n = n₁ + n₂ + ... + nₖ），则：
- 整体排序：n²
- 分开排序：n₁² + n₂² + ... + nₖ²
几何直观：把 n² 想象成正方形面积，n₁² + n₂² + ... + nₖ² 是边上小正方形面积之和，显然小于整个正方形面积。
结论：分开排序的时间复杂度总和小于整体排序，这就是桶排序的数学基础。
基本原理
桶排序的核心问题
| 问题 | 说明 |
|---|---|
| 如何分配元素到桶？ | 需决定桶的数量 k，并设计映射函数 |
| 如何对每个桶排序？ | 可用任意排序算法，或递归使用桶排序 |
| 如何合并有序桶？ | 需 O(n) 时间合并，否则退化为其他排序 |
时间复杂度分析
| 桶数量 k | 时间复杂度 | 对应算法 |
|---|---|---|
| k = 1 | O(n²) | 退化为选择排序 |
| 1 < k < n | < O(n²)，接近 O(n) | 典型桶排序 |
| k = n（每桶最多1个元素） | O(n) | 计数排序 |
前提：合并操作需在 O(n) 时间内完成，否则总时间复杂度会增加。
相关概念
- 计数排序：桶排序的特例，k 足够大时桶排序退化为计数排序
- 归并排序：类似桶排序的分治思想，但固定二分
- 选择排序：O(n²) 排序，用于数学证明对比
- 堆排序：文章提及作为对比（合并操作不适用二叉堆）
- 二叉堆：文章提及，但指出合并 k 个有序桶不适用二叉堆（O(n log k) 太慢）
- 桶排序：
相关实体
- labuladong：算法学习平台，本文来源
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 912. Sort an Array | 中等 |
| 力扣 | 912. 排序数组 | 中等 |
总结
桶排序是排序算法的「通用框架」：通过灵活选择桶数量 k 和映射函数，可以在归并排序（k=2）和计数排序（k=n）之间自由切换。其数学本质是「分而治之」——分开排序的总复杂度低于整体排序。