对于序列中的相同元素，如果排序之后它们的相对位置没有发生改变，则称该排序算法为「稳定排序」，反之则为「不稳定排序」
原地排序就是指排序过程中不需要额外的辅助空间，只需要常数级别的额外空间，直接操作原数组进行排序。
选择排序
选择排序是最简单朴素的排序算法，但是时间复杂度较高，且不是稳定排序。其他基础排序算法都是基于选择排序的优化。
思想：从小到大排序，从0开始每次遍历数组，找到最小的，最小的和0交换，然后找第二小的，依次排完。
C++实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <iostream>
#include <vector>
void selectSort(std::vector<int>& nums) {
int n = nums.size();
// sortedIndex 是一个分割线
// 索引 < sortedIndex 的元素都是已排序的
// 索引 >= sortedIndex 的元素都是未排序的
// 初始化为 0，表示整个数组都是未排序的
int sortedIndex = 0;
while (sortedIndex < n) {
// 找到未排序部分 [sortedIndex, n) 中的最小值
int minIndex = sortedIndex;
for (int i = sortedIndex + 1; i < n; i++) {
if (nums[i] < nums[minIndex]) {
minIndex = i;
}
}
// 交换最小值和 sortedIndex 处的元素
int tmp = nums[sortedIndex];
nums[sortedIndex] = nums[minIndex];
nums[minIndex] = tmp;
// sortedIndex 后移一位
sortedIndex++;
}
}
|
冒泡排序
冒泡算法是对选择排序的一种优化，通过交换 nums[sortedIndex] 右侧的逆序对完成排序，是一种稳定排序算法。
选择排序的几个待优化的问题：
1、选择排序算法是个不稳定排序算法，因为每次都要交换最小元素和当前元素的位置，这样可能会改变相同元素的相对位置。
2、选择排序的时间复杂度和初始数据的有序度完全没有关系，即便输入的是一个已经有序的数组，选择排序的时间复杂度依然是 O(n^2)。
3、选择排序的时间复杂度是 O(n^2)，具体的操作次数大概是 n^2/2 次，常规的优化思路无法降低时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <iostream>
#include <vector>
// 进一步优化，数组有序时提前终止算法
void bubbleSort(std::vector<int>& nums) {
int n = nums.size();
int sortedIndex = 0;
while (sortedIndex < n) {
// 加一个布尔变量，记录是否进行过交换操作
bool swapped = false;
for (int i = n - 1; i > sortedIndex; i--) {
if (nums[i] < nums[i - 1]) {
// swap(nums[i], nums[i - 1])
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
swapped = true;
}
}
// 如果一次交换操作都没有进行，说明数组已经有序，可以提前终止算法
if (!swapped) {
break;
}
sortedIndex++;
}
}
|
插入排序
插入排序是基于选择排序的一种优化，将 nums[sortedIndex] 插入到左侧的有序数组中。对于有序度较高的数组，插入排序的效率比较高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <vector>
// 对选择排序进一步优化，向左侧有序数组中插入元素
// 这个算法有另一个名字，叫做插入排序
void insertSort(std::vector<int>& nums) {
int n = nums.size();
// 维护 [0, sortedIndex) 是有序数组
int sortedIndex = 0;
while (sortedIndex < n) {
// 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
for (int i = sortedIndex; i > 0; i--) {
if (nums[i] < nums[i - 1]) {
// swap(nums[i], nums[i - 1])
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
} else {
break;
}
}
sortedIndex++;
}
}
|
插入排序的空间复杂度是 O(1)，是原地排序算法。时间复杂度是 O(n^2)。具体的操作次数和选择排序类似，是一个等差数列求和，大约是 n^2 /2 次。
插入排序是一种稳定排序，因为只有在 nums[i] < nums[i - 1] 的情况下才会交换元素，所以相同元素的相对位置不会发生改变。
插入排序的综合性能应该要高于冒泡排序。
冒泡排序的操作数大约是 n^2/2，而插入排序的操作数会小于 n^2/2。
希尔排序
希尔排序是基于插入排序的简单改进，通过预处理增加数组的局部有序性，突破了插入排序的O(N^2) 时间复杂度。
h 有序数组（h-sorted array）
定义
一个数组是 h 有序的（h-sorted），是指：
对于任意索引 i，只要 i + h < n，就有 arr[i] <= arr[i + h]。
换句话说，将数组按步长 h 分成若干子序列（每个子序列由间隔为 h 的元素组成），每个子序列内部都是有序的。
示例
设数组为：
1
| [9, 1, 8, 2, 7, 3, 6, 4, 5]
|
当 h = 3 时，分成 3 个子序列：
- 子序列 0: 索引 0, 3, 6 →
[9, 2, 6] - 子序列 1: 索引 1, 4, 7 →
[1, 7, 4] - 子序列 2: 索引 2, 5, 8 →
[8, 3, 5]
如果每个子序列都各自有序（如 [2, 6, 9], [1, 4, 7], [3, 5, 8]），则整个数组是 3-有序 的。
✅ h 越小，数组越“接近完全有序”；当 h = 1 时，就是普通插入排序，此时若有序，则整体有序。
希尔排序（Shell Sort）
核心思想
希尔排序是 插入排序的改进版，通过以下两步提升效率：
- 预处理阶段：
选择一个递减的 h 序列（如 ..., 127, 31, 7, 3, 1），对数组依次进行 h-有序化。 - 最终排序：
当 h = 1 时，执行一次插入排序 —— 此时数组已“基本有序”，插入排序效率接近 O(N)。
💡 关键：大的 h 值让元素快速“跳跃”到大致正确位置，避免小步挪动。
h 序列的选择
常见序列：
- Shell 原始序列：
⌊N/2⌋, ⌊N/4⌋, ..., 1（最简单，但性能一般） - Knuth 序列：
(3^k - 1)/2，如 1, 4, 13, 40, ...（推荐） - Sedgewick 序列：更优，但复杂
由于元素在不同 h 子序列间跳跃，无法保证相等元素的相对顺序，故希尔排序是不稳定排序。
时空复杂度分析
| 项目 | 复杂度 | 说明 |
|---|
| 时间复杂度 | 依赖 h 序列
• 最坏：O(N²)（如用 Shell 原始序列）
• 平均：O(N^{1.3}) ~ O(N^{1.5})
• 最好：O(N log N)（某些序列） | Knuth 序列平均约 O(N^{1.25}) |
| 空间复杂度 | O(1) | 原地排序 |
| 比较次数 | 远少于 O(N²) | 预处理大幅减少逆序对 |
C++ 实现（使用 Knuth 序列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <iostream>
#include <vector>
void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 1. 生成 Knuth 序列: 1, 4, 13, 40, ...
int h = 1;
while (h < n / 3) {
h = 3 * h + 1; // h = (3^k - 1) / 2
}
// 2. 从大到小使用 h 序列
while (h >= 1) {
// 对每个子序列执行插入排序
for (int i = h; i < n; ++i) {
int key = arr[i];
int j = i;
// 在子序列中向前比较（步长为 h）
while (j >= h && arr[j - h] > key) {
arr[j] = arr[j - h];
j -= h;
}
arr[j] = key;
}
h /= 3; // 下一个更小的 h
}
}
|
算法说明
- 内层
while 是 带步长 h 的插入排序 - 外层
h 从大到小，逐步精细化排序 - 时间复杂度取决于
h 序列，Knuth 序列实践效果良好
总结
| 特性 | 说明 |
|---|
| h 有序数组 | 每个间隔为 h 的子序列内部有序 |
| 希尔排序 | 多轮 h-插入排序，h 递减至 1 |
| 稳定性 | ❌ 不稳定 |
| 时间复杂度 | O(N^{1.3}) ~ O(N²)，依赖 h 序列 |
| 空间复杂度 | O(1) |
| 适用场景 | 中等规模数据、内存受限环境 |
✅ 希尔排序虽不如快排/归并高效，但因其 简单、原地、无递归、缓存友好，仍在嵌入式系统或教学中使用。
快速排序
快速排序的核心思想是 “分治 + 原地分区”，其关键在于 partition（分区）操作。
类似于二叉树的前置遍历，快速排序的 partition 操作可以看作是 “选择一个基准值（pivot），把小于它的放左边，大于它的放右边，然后递归处理左右两部分”。
分区（Partition）过程
- 选择一个 pivot（通常选最后一个元素）；
- 维护一个指针
i，表示“小于 pivot 的区域”的右边界； - 遍历数组，若当前元素
< pivot，则与 i 位置交换，并 i++； - 最后将 pivot 与
i 位置交换，此时 pivot 已在最终排序位置； - 返回 pivot 的索引，用于划分左右子数组。
代码框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <vector>
#include <algorithm> // for std::swap
// 分区函数：将 arr[lo..hi] 分区，返回 pivot 的最终索引
int partition(std::vector<int>& arr, int lo, int hi) {
int pivot = arr[hi]; // 选择最后一个元素作为 pivot
int i = lo; // i 是“小于 pivot 区域”的右边界（初始为 lo）
for (int j = lo; j < hi; ++j) {
if (arr[j] < pivot) {
std::swap(arr[i], arr[j]);
i++;
}
}
std::swap(arr[i], arr[hi]); // 将 pivot 放到正确位置
return i;
}
// 快速排序主函数
void quickSort(std::vector<int>& arr, int lo, int hi) {
if (lo >= hi) return; // 基线条件：子数组长度 <= 1
int p = partition(arr, lo, hi); // 前序位置：确定 pivot 位置
quickSort(arr, lo, p - 1); // 递归左子数组
quickSort(arr, p + 1, hi); // 递归右子数组
}
// 便捷调用接口
void quickSort(std::vector<int>& arr) {
if (arr.empty()) return;
quickSort(arr, 0, arr.size() - 1);
}
|
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|
| 最好情况 | O(N log N) | 每次 pivot 都将数组平分（如随机化 pivot） |
| 平均情况 | O(N log N) | 实践中非常高效 |
| 最坏情况 | O(N²) | 数组已有序，且每次选首/尾为 pivot（退化为冒泡） |
✅ 优化建议：使用 随机化 pivot 或 三数取中 可避免最坏情况。
空间复杂度
💡 可通过 尾递归优化 或 迭代+栈 将最坏空间降至 O(log N)，但 C++ 一般不自动优化尾递归。
稳定性
❌ 快速排序是 不稳定 的！
原因：
在 partition 过程中，相等元素可能因交换而改变相对顺序。
总结
| 项目 | 内容 |
|---|
| 核心思路 | 分治 + 原地分区，类比二叉树前序遍历 |
| 代码框架 | partition + 递归左右子数组（C++ 实现见上） |
| 时间复杂度 | 平均 O(N log N)，最坏 O(N²) |
| 空间复杂度 | 平均 O(log N)，最坏 O(N) |
| 稳定性 | ❌ 不稳定 |
✅ 快速排序是 实践中最快的通用排序算法之一，广泛用于 std::sort（Introsort 混合策略）等底层实现。
归并排序
归并排序的核心思想是 “分治 + 合并”，其关键在于 “先递归排序左右子数组，再合并两个有序数组”。
类似于二叉树后续遍历，“把数组从中间劈开，递归地让左右两边有序，然后像拉链一样合并成一个整体有序数组。”
合并（Merge）过程
- 创建临时数组
temp 存储 arr[lo..hi]； - 用双指针
i（左半）、j（右半）遍历两个有序子数组； - 每次取较小者放入原数组
arr，直到一方耗尽； - 将剩余元素全部拷回。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <vector>
// 合并两个有序子数组 arr[lo..mid] 和 arr[mid+1..hi]
void merge(std::vector<int>& arr, int lo, int mid, int hi) {
// 1. 复制到临时数组
std::vector<int> temp(arr.begin() + lo, arr.begin() + hi + 1);
// 2. 双指针合并
int i = 0; // temp 左半起始索引 (对应 arr[lo])
int j = mid - lo + 1; // temp 右半起始索引 (对应 arr[mid+1])
int k = lo; // 原数组写入位置
while (i <= mid - lo && j <= hi - lo) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 3. 拷回剩余元素（左半或右半）
while (i <= mid - lo) arr[k++] = temp[i++];
while (j <= hi - lo) arr[k++] = temp[j++];
}
// 归并排序主函数
void mergeSort(std::vector<int>& arr, int lo, int hi) {
if (lo >= hi) return; // 基线条件：子数组长度 <= 1
int mid = lo + (hi - lo) / 2; // 防止溢出
mergeSort(arr, lo, mid); // 递归左半
mergeSort(arr, mid + 1, hi); // 递归右半
merge(arr, lo, mid, hi); // 后序位置：合并
}
// 便捷调用接口
void mergeSort(std::vector<int>& arr) {
if (arr.empty()) return;
mergeSort(arr, 0, arr.size() - 1);
}
|
排序稳定性
✅ 归并排序是 稳定 的！
原因：
在 merge 过程中，当左右元素相等时，优先取左边的元素（if (temp[i] <= temp[j])），从而保持了原始相对顺序。
📌 稳定性定义：相等元素在排序后相对位置不变。
归并排序是 少数同时具备 O(N log N) 时间复杂度和稳定性的排序算法。
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|
| 最好 / 平均 / 最坏 | O(N log N) | 无论输入如何，always 分成两半 + 线性合并 |
✅ 归并排序的时间复杂度非常稳定，无退化情况。
是否是原地排序？
❌ 归并排序 不是原地排序！
- 空间复杂度：O(N)
主要消耗在 merge 函数中的临时数组 temp（需额外 O(N) 空间）。 - 虽然递归栈深度为 O(log N)，但主导项是 O(N) 的辅助空间。
💡 对比：快速排序是原地排序（O(1) 辅助空间，不计递归栈），但不稳定；
归并排序稳定且时间稳定，但需额外空间。
总结
| 项目 | 内容 |
|---|
| 核心思路 | 分治 + 后序合并，类比二叉树后序遍历 |
| 排序稳定性 | ✅ 稳定（相等元素保持原序） |
| 时间复杂度 | O(N log N)（所有情况） |
| 是否原地排序 | ❌ 否，需 O(N) 额外空间 |
| 适用场景 | 需要稳定排序、外部排序（如大文件排序） |
✅ 归并排序是 理论最优的稳定排序算法，也是 Java Collections.sort()、Python sorted() 等底层实现的基础（Timsort 是其变种）。
堆排序
思路
最直观的做法：把所有元素插入一个最小堆（或最大堆），然后依次弹出，即可得到有序序列。
- 使用优先级队列（底层是二叉堆）作为辅助数据结构；
- 插入 N 个元素：O(N log N)；
- 弹出 N 个元素：O(N log N)；
- 缺点：需要 O(N) 额外空间，不符合“原地排序”要求。
实现（使用 std::priority_queue）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <vector>
#include <queue>
// 升序排序：使用最大堆，从后往前填
void heapSortSimple(std::vector<int>& nums) {
std::priority_queue<int> maxHeap; // 默认是最大堆
// 1. 所有元素入堆
for (int x : nums) {
maxHeap.push(x);
}
// 2. 从堆顶取出最大值，倒序放入数组
for (int i = nums.size() - 1; i >= 0; --i) {
nums[i] = maxHeap.top();
maxHeap.pop();
}
}
|
✅ 正确性高，代码简洁
❌ 空间复杂度 O(N)，非原地排序
优化（原地堆排序）
核心思想
不创建额外堆，而是直接将输入数组视为完全二叉树，通过 sink 操作原地构建最大堆，并完成排序。
两个关键步骤：
原地建堆（Heapify）
- 从最后一个非叶子节点开始（索引为
n/2 - 1），自底向上执行 sink； - 时间复杂度仅为 O(N)（不是 O(N log N)！）。
原地排序（Sort）
- 将堆顶（最大值）与堆尾交换；
- 缩小堆范围（排除已排序部分）；
- 对新堆顶执行
sink，恢复堆性质； - 重复直到堆只剩一个元素。
💡 这就是标准的 原地堆排序（In-place Heap Sort），空间复杂度 O(1)。
辅助函数：sink（下沉操作）
1
2
3
4
5
6
7
8
9
10
11
12
13
| // 维护最大堆性质：将索引 k 的元素下沉到合适位置
// n 表示当前堆的有效大小（[0, n) 范围内）
void sink(std::vector<int>& arr, int k, int n) {
while (2 * k + 1 < n) { // 存在左子节点
int j = 2 * k + 1; // 左子节点索引
if (j + 1 < n && arr[j] < arr[j + 1]) {
j++; // 选择较大的子节点（右子节点）
}
if (arr[k] >= arr[j]) break; // 已满足堆性质
std::swap(arr[k], arr[j]);
k = j; // 继续下沉
}
}
|
优化版堆排序（原地，O(1) 空间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <vector>
#include <algorithm> // for std::swap
void heapSort(std::vector<int>& nums) {
int n = nums.size();
// 1. 原地建堆：从最后一个非叶子节点开始 sink
for (int i = n / 2 - 1; i >= 0; --i) {
sink(nums, i, n);
}
// 2. 排序：每次将堆顶移到末尾
for (int i = n - 1; i > 0; --i) {
std::swap(nums[0], nums[i]); // 最大值放到已排序区
sink(nums, 0, i); // 对 [0, i) 重建堆
}
}
|
✅ 时间复杂度：O(N log N)
✅ 空间复杂度：O(1)（无递归，纯迭代）
✅ 原地排序，符合堆排序标准定义
堆排序的稳定性
✅ 堆排序无法保证相等元素的相对顺序，故不稳定。
完整可运行示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <vector>
#include <algorithm>
void sink(std::vector<int>& arr, int k, int n) {
while (2 * k + 1 < n) {
int j = 2 * k + 1;
if (j + 1 < n && arr[j] < arr[j + 1]) j++;
if (arr[k] >= arr[j]) break;
std::swap(arr[k], arr[j]);
k = j;
}
}
void heapSort(std::vector<int>& nums) {
int n = nums.size();
// 建堆
for (int i = n / 2 - 1; i >= 0; --i)
sink(nums, i, n);
// 排序
for (int i = n - 1; i > 0; --i) {
std::swap(nums[0], nums[i]);
sink(nums, 0, i);
}
}
|
总结
| 项目 | 内容 |
|---|
| 简单实现 | 使用 priority_queue，逻辑清晰但需 O(N) 空间 |
| 优化实现 | 原地建堆 + sink，O(1) 空间，标准堆排序 |
| 时间复杂度 | 建堆 O(N) + 排序 O(N log N) → 总 O(N log N) |
| 空间复杂度 | O(1)（迭代实现，无递归栈） |
| 稳定性 | ❌ 不稳定 |
✅ 堆排序是少数能在 最坏情况 O(N log N) 下运行的原地排序算法，适用于内存受限或对最坏性能有要求的场景。
计数排序
通用的计数排序（支持负数）
核心思想
计数排序适用于 整数范围有限 的场景。对于包含负数的数组，不能直接用元素值作 count 数组下标（因为下标不能为负）。
✅ 解决方案：
引入 偏移量（offset），将所有元素映射到非负区间。
设：
min_val = min(nums)max_val = max(nums)range = max_val - min_val + 1
则任意元素 x 对应的计数数组索引为：
1
| index = x - min_val // 保证 index >= 0
|
处理负数和自定义类型
1. 负数处理 ✅
如上所述，通过 offset = -min_val 将负数“平移”到非负域。
示例：nums = [-2, -1, 0, 1, 2]
min = -2, offset = 2 → 映射为 [0, 1, 2, 3, 4]
2. 自定义类型（需以整数为键）
计数排序要求：
因此：
- 不能直接排序任意结构体/对象；
- 但若对象有整数 ID 且范围小，可基于 ID 排序（需额外存储原始对象）。
⚠️ 计数排序仅适用于整数或可离散化为小范围整数的类型。
累加 count 数组（实现稳定排序）
关键技巧：前缀和（Prefix Sum）
为了使计数排序 稳定（相同元素保持原相对顺序），需对 count 数组做前缀和累加，使其表示“小于等于该值的元素个数”。
步骤：
- 统计频次：
count[x - min]++ - 累加前缀和：
count[i] += count[i-1]（从左到右） - 从后往前遍历原数组，将元素放入结果数组的
count[index] - 1 位置，并 count[index]--
💡 从后往前遍历 + 前缀和 → 保证稳定性！
实现（通用、稳定、支持负数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| std::vector<int> countingSort(const std::vector<int>& nums) {
if (nums.empty()) return {};
int min_val = *std::min_element(nums.begin(), nums.end());
int max_val = *std::max_element(nums.begin(), nums.end());
int range = max_val - min_val + 1;
std::vector<int> count(range, 0);
for (int x : nums) {
count[x - min_val]++;
}
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
std::vector<int> result(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int idx = nums[i] - min_val;
result[count[idx] - 1] = nums[i];
count[idx]--;
}
return result;
}
|
✅ 支持负数
✅ 稳定排序
✅ 原地？否（返回新数组，符合函数式风格；也可改写为 in-place）
时空复杂度分析
| 项目 | 复杂度 | 说明 |
|---|
| 时间复杂度 | O(n + k) | n = nums.size(), k = max - min + 1（值域大小） |
| 空间复杂度 | O(k + n) | count 数组 O(k)，结果数组 O(n) |
| 是否原地 | 否 | 需要额外 O(n) 输出空间（若要求稳定） |
⚠️ 当 k >> n（如 max=1e9, min=0），计数排序效率极低，甚至内存溢出。
✅ 计数排序是典型的 非比较排序
- 不通过元素间比较 决定顺序；
- 而是通过 统计频次 + 数学映射 直接确定位置；
- 因此可以突破 比较排序的 O(n log n) 下界，达到 O(n + k)。
📌 其他非比较排序：桶排序、基数排序。
总结
| 特性 | 说明 |
|---|
| 通用性 | 支持负数（通过偏移量），不支持大范围或浮点数 |
| 稳定性 | ✅ 通过前缀和 + 逆序填充实现 |
| 时间复杂度 | O(n + k)，k 为值域大小 |
| 空间复杂度 | O(n + k) |
| 排序类型 | 非比较排序 |
| 适用场景 | 整数、值域小（如成绩 0100、颜色 02） |
桶排序
桶排序的关键点
桶排序的核心思想是 “分而治之 + 归并”，其关键在于以下三点：
将待排序数组划分为若干个“桶”（子区间）
- 每个桶对应一个值域范围（如
[0,1), [1,2) 等）； - 元素通过映射函数（如
floor(x * k)）分配到对应桶中。
对每个桶内部单独排序
- 可使用任意排序算法（常用插入排序，因桶内数据少且近似有序）；
- 也可递归使用桶排序（适用于浮点数或大范围数据）。
按顺序合并所有桶
- 因桶的值域互不重叠且有序，直接拼接即可得到全局有序序列；
- 合并时间复杂度为 O(n)。
💡 桶排序可看作 归并排序（分治） + 计数排序（值域划分） 的结合体。
映射函数（将元素分配到 k 个桶中）
对于 k 个桶，每个桶覆盖区间长度为 1.0 / k。
元素 x ∈ [0, 1) 映射到桶索引：
1
2
| int bucketIndex = static_cast<int>(x * k);
// 注意：当 x == 1.0 时需特殊处理（但通常 x < 1）
|
✅ 保证：bucket[i] 中所有元素 ∈ [i/k, (i+1)/k)
使用插入排序的桶排序（推荐）
C++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #ifndef BUCKET_SORT_H
#define BUCKET_SORT_H
#include <vector>
#include <algorithm>
#include <cmath>
// 插入排序（用于小数组）
inline void insertionSort(std::vector<double>& arr) {
for (size_t i = 1; i < arr.size(); ++i) {
double key = arr[i];
int j = static_cast<int>(i) - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
// 桶排序（支持任意范围浮点数）
inline void bucketSort(std::vector<double>& nums) {
if (nums.empty()) return;
// 1. 找到最大最小值
double min_val = nums[0];
double max_val = nums[0];
for (double x : nums) {
if (x < min_val) min_val = x;
if (x > max_val) max_val = x;
}
if (min_val == max_val) return;
int n = nums.size();
std::vector<std::vector<double>> buckets(n); // 创建 n 个桶
// 2. 分配元素到桶
double range = max_val - min_val;
for (double x : nums) {
// 映射到 [0, n-1]
int idx = static_cast<int>((x - min_val) / range * n);
if (idx >= n) idx = n - 1;
if (idx < 0) idx = 0;
buckets[idx].push_back(x);
}
// 3. 对每个桶排序
for (auto& bucket : buckets) {
insertionSort(bucket);
}
// 4. 合并桶
int index = 0;
for (const auto& bucket : buckets) {
for (double x : bucket) {
nums[index++] = x;
}
}
}
#endif // BUCKET_SORT_H
|
✅ 时间复杂度期望 O(n)，空间 O(n)
✅ 稳定（若插入排序稳定）
使用递归的桶排序（适用于更广范围）
当数据范围大或分布不均时，可对非空桶递归调用桶排序。
C++ 实现（递归版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #ifndef RECURSIVE_BUCKET_SORT_H
#define RECURSIVE_BUCKET_SORT_H
#include <vector>
#include <algorithm>
#include "bucket_sort.h" // Need insertionSort
inline void recursiveBucketSort(std::vector<double>& nums, int depth = 0) {
const int MAX_DEPTH = 5; // 防止无限递归
if (nums.size() <= 1 || depth >= MAX_DEPTH) {
insertionSort(nums);
return;
}
// 1. 找到最大最小值
double min_val = nums[0];
double max_val = nums[0];
for (double x : nums) {
if (x < min_val) min_val = x;
if (x > max_val) max_val = x;
}
if (min_val == max_val) return;
int n = nums.size();
std::vector<std::vector<double>> buckets(n);
double range = max_val - min_val;
for (double x : nums) {
int idx = static_cast<int>((x - min_val) / range * n);
if (idx >= n) idx = n - 1;
if (idx < 0) idx = 0;
buckets[idx].push_back(x);
}
nums.clear();
for (auto& bucket : buckets) {
if (!bucket.empty()) {
recursiveBucketSort(bucket, depth + 1);
nums.insert(nums.end(), bucket.begin(), bucket.end());
}
}
}
#endif // RECURSIVE_BUCKET_SORT_H
|
⚠️ 递归版适用于数据分布不均匀的场景，但需控制深度防止栈溢出。
排序的稳定性
✅ 桶排序可以是 稳定的
- 前提：桶内排序算法是稳定的（如插入排序）；
- 原因：
- 相同值的元素会被分到同一个桶；
- 桶内稳定排序保持其相对顺序；
- 合并时按桶顺序拼接，不改变跨桶相同值的顺序（但跨桶不会有相同值，因值域不重叠）。
📌 结论：若桶内排序稳定，则整体桶排序稳定。
时空复杂度分析
| 项目 | 复杂度 | 说明 |
|---|
| 时间复杂度（平均） | O(n + k) | k 为桶数，通常取 k = n；桶内排序总代价期望 O(n) |
| 时间复杂度（最坏） | O(n²) | 所有元素落入同一桶，退化为插入排序 |
| 空间复杂度 | O(n + k) | 存储 k 个桶，总元素数 n |
| 是否原地 | ❌ 否 | 需要额外 O(n) 空间 |
✅ 当输入 均匀分布 时，桶排序性能接近线性，优于 O(n log n) 的比较排序。
适用场景 vs 限制
| 优点 | 缺点 |
|---|
| ✅ 平均时间复杂度 O(n) | ❌ 依赖输入分布（需近似均匀） |
| ✅ 稳定（配合稳定子排序） | ❌ 最坏情况退化为 O(n²) |
| ✅ 适合浮点数、小范围整数 | ❌ 不适合值域过大或未知的数据 |
💡 经典应用：对 [0,1) 浮点数排序、成绩分布统计等。
总结
| 内容 | 说明 |
|---|
| 关键点 | 分桶 → 桶内排序 → 合并 |
| 分配到 k 桶 | idx = floor(x * k)（x ∈ [0,1)） |
| 桶内排序 | 常用插入排序（小数据高效） |
| 递归桶排序 | 应对非均匀分布 |
| 稳定性 | ✅ 可稳定（依赖子排序） |
| 时间复杂度 | 平均 O(n)，最坏 O(n²) |
| 空间复杂度 | O(n) |
| 排序类型 | 非比较排序 |
✅ 桶排序是 理论优美、实践受限 的算法——在合适场景下（如均匀分布浮点数），它是最快的排序之一。
基数排序
基数排序（Radix Sort）是一种 非比较排序算法，其核心思想是：
将整数按“位”拆分（如个位、十位、百位…），从低位到高位（或高位到低位）依次对每一位进行稳定排序，最终得到全局有序序列。
- 它是 计数排序的扩展：对每一位使用计数排序；
- 要求待排序数据为 整数（或可映射为整数，如字符串）；
- 关键依赖：每一位的排序必须是稳定的。
✅ 示例（LSD 方式）：
1
2
3
4
| 初始: [329, 457, 839, 439, 720, 355, 350]
按个位排序 → [720, 350, 355, 457, 329, 839, 439]
按十位排序 → [720, 329, 839, 439, 350, 355, 457]
按百位排序 → [329, 350, 355, 439, 457, 720, 839] ✅
|
为什么对每一位必须使用稳定排序？
假设对十位排序时使用不稳定排序：
- 在个位排序后，
350 在 355 前（因 0 < 5）； - 若十位排序时两者十位相同（都是 5），但不稳定排序交换了它们的位置；
- 最终结果中
355 会排在 350 前 → 破坏整体顺序。
✅ 结论：
只有稳定排序能保证 “高位相同时，低位已排好的顺序不被破坏”。
使用什么稳定排序比较好？
推荐：计数排序（Counting Sort）
- 时间复杂度 O(n + k)，k = 10（0~9 数字）→ 实际为 O(n)；
- 空间开销小（仅需长度为 10 的 count 数组）；
- 天然支持数字位排序。
其他稳定排序（如插入排序）也可用，但效率远低于计数排序。
位数不同怎么办
解决方案：统一按最大位数处理
- 找出数组中最大值
maxVal，计算其位数 d = floor(log10(maxVal)) + 1； - 位数不足的数视为高位补 0（如 5 视为 005）；
- 计数排序天然支持（取某位数字时，高位不存在即为 0）。
💡 无需显式补零，只需在取第 k 位时做数学运算即可。
有负数怎么办？
解决方案：偏移法（Offset）
- 找出最小值
minVal； - 将所有元素加上
offset = -minVal，转为非负整数； - 执行基数排序；
- 排序后减去
offset，恢复原始值。
⚠️ 注意：此方法仅适用于整数，且需确保加法不溢出。
必须从低位到高位吗？（LSD vs MSD）
| 类型 | 全称 | 顺序 | 特点 |
|---|
| LSD | Least Significant Digit | 从低位 → 高位 | ✅ 实现简单，常用；要求排序算法稳定 |
| MSD | Most Significant Digit | 从高位 → 低位 | 适合字符串排序；递归分治，实现复杂 |
✅ 整数排序通常用 LSD（因为位数固定，LSD 更高效）；
✅ 字符串/变长数据用 MSD（可提前终止比较）。
MSD 算法逻辑（简要）
- 从最高位开始；
- 按当前位将数组分到 10 个桶（0~9）；
- 对每个非空桶，递归处理下一位；
- 合并所有桶（自然有序）。
⚠️ MSD 需处理前导零、位数不一致等问题，且递归深度大，实践中较少用于整数排序。
LSD 基数排序 C++ 实现（支持负数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <vector>
#include <algorithm>
#include <climits>
// 对第 exp 位（1, 10, 100...）进行计数排序
void countingSortForRadix(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
std::vector<int> count(10, 0); // 0~9
// 统计当前位频次
for (int i = 0; i < n; ++i) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 前缀和（变为“<= digit”的个数）
for (int i = 1; i < 10; ++i) {
count[i] += count[i - 1];
}
// 从后往前填充（保证稳定）
for (int i = n - 1; i >= 0; --i) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// 写回原数组
for (int i = 0; i < n; ++i) {
arr[i] = output[i];
}
}
// 基数排序（支持负数）
void radixSort(std::vector<int>& nums) {
if (nums.empty()) return;
// 1. 处理负数：偏移至非负
int min_val = *std::min_element(nums.begin(), nums.end());
int offset = (min_val < 0) ? -min_val : 0;
if (offset > 0) {
for (int& x : nums) x += offset;
}
// 2. 找最大值以确定位数
int max_val = *std::max_element(nums.begin(), nums.end());
// 3. LSD: 从个位开始
for (int exp = 1; max_val / exp > 0; exp *= 10) {
countingSortForRadix(nums, exp);
}
// 4. 恢复负数
if (offset > 0) {
for (int& x : nums) x -= offset;
}
}
|
时空复杂度及稳定性
| 项目 | 复杂度/性质 | 说明 |
|---|
| 时间复杂度 | O(d × (n + k)) | d = 位数，k = 10（数字基数），通常简化为 O(d·n) |
| 空间复杂度 | O(n + k) | 计数排序需要 O(k) 辅助空间，输出数组 O(n) |
| 稳定性 | ✅ 稳定 | 因每一位都使用稳定排序（计数排序） |
| 是否比较排序 | ❌ 非比较排序 | 不依赖元素比较，突破 O(n log n) 下界 |
💡 当 d 为常数（如 32 位整数最多 10 位十进制数），时间复杂度为 O(n)。
总结
| 问题 | 答案 |
|---|
| 原理 | 按位拆分，逐位稳定排序 |
| 为何要稳定 | 保持低位已排好的顺序 |
| 推荐子排序 | 计数排序（高效、稳定） |
| 位数不同 | 按最大位数处理，高位补 0 |
| 负数处理 | 偏移法转为非负 |
| LSD vs MSD | 整数用 LSD，字符串用 MSD |
| 稳定性 | ✅ 稳定 |
| 时间复杂度 | O(d·n) |
| 空间复杂度 | O(n) |
✅ 基数排序是 线性时间排序 的代表，在整数范围可控时性能极佳，广泛用于数据库、嵌入式系统等场景。
Reference
https://labuladong.online/algo/data-structure-basic/sort-basic/