📋 摘要
- 覆盖十大排序：冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数，每个都配原理、复杂度、C++ 标准实现与 Excalidraw 图解。
- 复杂度判断的方法论统一放在 算法复杂度，本文开头只给速览。
- 主线：比较排序分「O(n²) 简单三件套」与「O(n log n) 三巨头」；非比较排序（计数/桶/基数）依赖值域或位，可达线性时间。
- 稳定性：冒泡、插入、归并、计数、基数、桶稳定；选择、快速、堆、希尔不稳定。
算法复杂度判断速览
拿到一段代码或一个算法，复杂度怎么估？核心规则只有几条（完整推导见 算法复杂度）：
- 顺序语句相加、嵌套循环相乘：单层循环 O(n)，双层嵌套 O(n²)。
- 每轮减半 / 二分查找 → O(log n)。
- 分治（每层做 O(n) 的划分/合并 × 共 O(log n) 层）→ O(n log n)，归并/快排/堆排都落在这条线上。
- 大 O 只保留增长最快的主导项，常数与低阶项被忽略。
📝 注意
下面每个算法的「复杂度」小节给出最好/平均/最坏时间、空间与稳定性；判断这些值的方法论与主定理，统一见 算法复杂度。
十大排序总览
| 算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n log n) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) | 稳定 |
💡 提示
小数据或近乎有序用插入排序（O(n) 起手）；通用内部排序首选快排；稳定性要求选归并或 std::stable_sort；值域小的整数用计数/基数，分布均匀用桶排序。
冒泡排序
原理
冒泡排序反复遍历数组，从头到尾比较每一对相邻元素，若前一个大于后一个就交换它们。每一轮遍历都会把当前未排序区间的最大值不断向右交换、最终”冒泡”到区间末尾。经过 n−1 轮后，整个数组有序。内层循环每轮收窄一位，因为末尾已就位的元素无需再参与比较。它只用”相邻比较 + 交换”这一最基础的操作，天然保证正确性且是稳定排序；并用 swapped 标志在某一轮未发生交换时提前结束，从而在基本有序时拿到最好 O(n)。
复杂度
- 时间：最好 O(n) / 平均 O(n²) / 最坏 O(n²)
- 空间：O(1)
- 稳定性：稳定——只有严格逆序
a[j] > a[j+1]时才交换，相等元素从不被交换，相对顺序保持不变。
图解
图解 1：算法思想与循环不变量
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <vector>
#include <cstddef>
#include <utility>
// 冒泡排序：每轮把未排序区间的最大值"冒泡"到末尾
template <typename T>
void bubbleSort(std::vector<T>& arr) {
const std::size_t n = arr.size();
for (std::size_t i = 0; i < n - 1; ++i) { // 轮次数，最多 n-1 轮
bool swapped = false; // early-exit 标志
for (std::size_t j = 0; j < n - i - 1; ++j) { // 相邻对的左下标，待比较区间逐轮收窄
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]); // 相邻逆序则交换
swapped = true;
}
}
if (!swapped) { // 本轮无交换 → 已有序
break;
}
}
}要点
- 适用场景：数据量小或基本有序时，因实现简单且带 early-exit 表现尚可；对大数据量 O(n²) 太慢，实际工程中很少选用。
- 面试加分点：能讲清”每轮把最大值/最小值沉到末尾”、稳定性的原因，以及最好 O(n) 来自 swapped 提前退出；常被用来对比选择排序与插入排序。
- 对比：与选择排序同为 O(n²)，但选择排序不稳定、交换次数少；插入排序在基本有序时更优，冒泡的交换开销是三者中最大的。
选择排序
原理
选择排序把数组看成两段：左边是已排序区（初始为空），右边是未排序区。每一轮，在未排序区里扫描一遍，找出最小值的下标 min_idx，然后把它与未排序区的第一个元素（下标 i）交换。交换之后，下标 i 的元素就落到了最终位置，已排序区向右扩展一位、未排序区缩小一位。重复 n−1 轮后，最后一个元素自然就位，数组完全有序。这样设计是为了把「交换」这一相对昂贵的写操作压到每轮一次、共 O(n) 次——代价是无论如何都要做约 n²/2 次比较。
复杂度
- 时间：最好 O(n²) / 平均 O(n²) / 最坏 O(n²)
- 空间：O(1)
- 稳定性：不稳定（跨距交换把最小值与未排序区首元素互换，跳过中间元素，破坏了相等元素的相对顺序）
图解
图解 1：算法思想与循环不变量
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <vector>
#include <utility> // std::swap
template <typename T>
void selectionSort(std::vector<T>& arr) {
const int n = static_cast<int>(arr.size());
for (int i = 0; i < n - 1; ++i) { // 未排序的第一个位置，左侧已排序，右侧未排序
int min_idx = i; // 假设未排序区首元素最小
for (int j = i + 1; j < n; ++j) { // 在未排序区找最小
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) { // 最小值不在原位才交换
std::swap(arr[i], arr[min_idx]);
}
}
}要点
- 适用场景：数据量小、或对「写次数」敏感时；比较次数恒为 O(n²)，但交换次数最多 n−1 次，是简单排序里写操作最少的之一。
- 面试加分点：复杂度与输入分布无关（最好/平均/最坏全 O(n²)），且不稳定（跨距交换打乱相等元素相对顺序），常与冒泡、插入对比提问。
- 对比：比冒泡少了大量交换（冒泡每轮可能多次交换），但任何情况下都不如插入排序（接近有序时 O(n)），实际几乎不用于通用排序。
插入排序
原理
插入排序把数组看成「已排序前缀」+「未排序后缀」两段，初始时前缀只含第一个元素。每一轮取出后缀第一个元素作为 key，从右往左扫描前缀：只要前面的元素大于 key，就把它向右挪一格，为 key 腾出插入位置。当遇到第一个不大于 key 的元素（或扫到数组最左端）时，把 key 填入空出的位置。如此逐轮把后缀元素并入前缀，直到全部有序。整个过程像整理扑克牌那样逐张插入，核心只有「比较 + 右移」两个操作，因此原地且实现直观。
复杂度
- 时间：最好 O(n)（数组已有序时每轮只比较一次）／平均 O(n²)／最坏 O(n²)（逆序时每轮都要移到最前）
- 空间：O(1)（原地排序，只使用 key、i、j 等常数个变量）
- 稳定性：稳定 —— 只右移严格大于 key 的元素（用
>而非>=），相等元素不会互换相对顺序。
图解
图解 1：算法思想与循环不变量
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <vector>
template <typename T>
void insertionSort(std::vector<T>& arr) {
int n = static_cast<int>(arr.size());
for (int i = 1; i < n; ++i) { // 未排序后缀的第一个元素
int key = arr[i];
int j = i - 1; // 已排序前缀的最后一个元素
while (j >= 0 && arr[j] > key) { // 比 key 大的元素依次右移，为 key 腾出位置
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key; // key 落位
}
}要点
- 适用场景：数据量小（n 较小时常数最小）或已基本有序的数组；标准库
std::sort（introsort）在小区间上就用插入排序收尾。 - 面试加分点：最好 O(n)、稳定、原地、可在线处理（边读边排）；对「部分有序」数据接近 O(n)，比同为 O(n²) 的选择/冒泡更实用。
- 对比：对逆序数据退化到 O(n²)，大规模改用 O(n log n) 算法，但插入排序常作为小规模子问题的基例。
希尔排序
原理
希尔排序是插入排序的改进：先把数组按间隔 gap 分成若干组——同组元素的下标相差 gap——并对每一组分别做插入排序；随后逐步减小 gap（本文用最经典的 Shell 序列 gap = n/2, n/4, …, 1），直到 gap = 1 退化为一次普通插入排序。它的核心操作与插入排序完全一致，只是比较和移动的对象从「相邻元素」变成了「相隔 gap 的元素」。这么设计是因为：gap 较大时元素一次能跨越多格，位于队首的大元素可以快速「跳」到队尾，数组很快从乱序变为「大致有序」。而插入排序对基本有序的序列几乎只需线性时间，所以最后 gap = 1 时只剩少量微调，整体比普通插入排序快得多。
复杂度
- 时间：最好 O(n log n) / 平均约 O(n^1.3) / 最坏 O(n²)（与间隔序列的选取有关）
- 空间：O(1)（原地排序）
- 稳定性：不稳定——相等元素可能落在不同的 gap 分组里，跨组交换会打乱它们的原始相对顺序。
图解
图解 1：算法思想与循环不变量
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <iostream>
#include <vector>
// 希尔排序：按 gap 分组做插入排序，gap 逐步减半直到 1
template <typename T>
void shellSort(std::vector<T>& arr) {
int n = static_cast<int>(arr.size());
for (int gap = n / 2; gap > 0; gap /= 2) { // gap: n/2, n/4, ..., 1
for (int i = gap; i < n; ++i) { // 每组做插入排序
T temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) { // 同组元素相隔 gap
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}要点
- 适用场景：中等规模数据，或对「大体有序、局部乱序」的序列效率很高；实现简单、常数小，是嵌入式/小型场景常用的轻量排序。
- 与插入排序的关系：希尔排序本质是「对相隔 gap 的元素序列反复做插入排序」，gap = 1 时就是普通插入排序；gap 序列选得越好，越接近 O(n log n)。
- 面试加分点：能讲清「为什么比插入排序快」——gap 让元素长距离跳跃、快速消除大量逆序，使最后一轮插入排序接近最优情形。
快速排序
原理
快速排序是分治思想的代表：每次先从区间里选一个基准 pivot，通过一次 partition 把小于 pivot 的元素都挪到它左边、不小于它的都挪到右边，使 pivot 落到最终有序位置。这个「选 pivot → partition → 递归」的三步就是它的全部机制。核心操作是 partition 内的单向扫描交换，用常数个下标（i 维护”小于区”边界、j 扫描）把区间切成两段。之所以这么设计，是因为 pivot 一旦归位就再也不用参与后续排序，问题规模每层都减半（平均情况），从而得到 O(n log n)。递归处理左右子区间，直到子区间为空或只剩一个元素为止。
复杂度
- 时间：最好 O(n log n) / 平均 O(n log n) / 最坏 O(n²)（每次 pivot 都取到最小/最大元素时退化为 O(n²)）
- 空间：O(log n)（平均情况下递归栈深度）
- 稳定性：不稳定——partition 交换时可能打乱相等元素之间的相对顺序
图解
图解 1：算法思想与分区不变量
图解 2：Partition 逐行执行
C++ 实现
❯C++
#include <vector>
#include <utility> // std::swap
// 划分：返回 pivot 最终下标，左边 < pivot，右边 >= pivot
template <typename T>
int partition(std::vector<T>& arr, int left, int right) {
T pivot = arr[right]; // 取末尾元素作基准
int i = left; // i 是「< pivot 区域」的下一个位置,也就是「>= pivot 区域」的起始位置
for (int j = left; j < right; ++j) {
if (arr[j] < pivot) {
std::swap(arr[i], arr[j]);
++i;
}
}
std::swap(arr[i], arr[right]); // pivot 归位
return i;
}
template <typename T>
void quickSort(std::vector<T>& arr, int left, int right) {
if (left >= right) { // 空或单元素，递归终止
return;
}
int p = partition(arr, left, right);
quickSort(arr, left, p - 1); // 左子区间
quickSort(arr, p + 1, right); // 右子区间
}要点
- 适用场景：一般内部排序首选，常数因子小、就地且缓存友好；配合随机 pivot / 三数取中，实践中几乎不会退化到最坏。
- 面试加分点：随机选 pivot 或三数取中可避免最坏 O(n²)；
std::sort实际是 introsort（快排 + 堆排兜底，深度过深时转堆排）。 - 与归并对比：归并稳定、稳定 O(n log n) 但需 O(n) 额外空间；快排不稳定、最坏 O(n²) 但空间 O(log n) 且就地更快。
堆排序
原理
堆排序把数组看作一棵完全二叉树：下标 i 的孩子是 2i+1、2i+2，父节点是 (i-1)/2。第一步建最大堆：从最后一个非叶节点（n/2-1）向上，对每个节点做 sift-down 下沉——把它与较大的孩子交换，直到「父 ≥ 子」。第二步反复「取出堆顶」：把堆顶（当前最大值）与堆末尾元素交换、堆大小减一，再对新堆顶下沉恢复堆性质。因为交换只需 O(1)、而每次下沉最多走树高 O(log n)，整体复杂度被稳定控制在 O(n log n)。
复杂度
- 时间：最好 O(n log n) / 平均 O(n log n) / 最坏 O(n log n)
- 空间：O(1)
- 稳定性：不稳定——堆顶与末尾的跨层交换会打乱等值元素的相对顺序。
图解
图解 1：算法思想与堆不变量
图解 2：Sift-down 逐行执行
C++ 实现
❯C++
#include <cstddef>
#include <utility>
#include <vector>
[// 将下标 i 的子树下沉为最大堆（n 为当前堆的大小）
template <typename T>
void siftDown(std::vector<T>& arr, std::size_t i, std::size_t n) {
while (true) {
std::size_t l = 2 * i + 1;
std::size_t r = 2 * i + 2;
std::size_t largest = i; // 父与两个子节点中最大的那个，假定父节点最大
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest == i) {
break;
}
std::swap(arr[i], arr[largest]);
i = largest;
}
}
// 从最后一个非叶节点向上建堆
template <typename T>
void heapify(std::vector<T>& arr) {
const std::size_t n = arr.size();
for (std::size_t i = n / 2; i > 0; --i) { // n/2是最后一个非叶节点的个数，注意索引从0开始，所以实际下标是 i-1
siftDown(arr, i - 1, n);
}
}
template <typename T>
void heapSort(std::vector<T>& arr) {
const std::size_t n = arr.size();
heapify(arr); // 建立最大堆
for (std::size_t end = n; end > 1; --end) {
std::swap(arr[0], arr[end - 1]); // 堆顶（最大值）移到末尾
siftDown(arr, 0, end - 1); // 剩余堆重新下沉
}
}]()要点
- 适用场景：Top-K（只维护大小为 K 的堆）、优先队列、流式数据求中位数等，不必全量排序。
- 面试加分点：自底向上建堆是 O(n) 而非 O(n log n)；原地排序、无递归栈、最坏情况仍 O(n log n)。
- 与快排对比：最坏可预期、不会退化到 O(n²)，但常数大、内存访问不连续，平均速度通常慢于快排。
归并排序
原理
归并排序用分治法：先把数组递归地对半拆成两半，直到每个子数组只剩一个元素（天然有序），再把两个已有序的子数组合并成一个有序数组，自底向上逐层归并回原数组。核心操作是「合并两个有序数组」——用双指针 i、j 同时扫描两个有序段，每次取较小的放进临时数组，某一侧耗尽后把另一侧剩余元素整体追加。之所以这么设计，是因为「合并两个有序数组」是 O(n) 的线性操作，而拆分只有 O(log n) 层，二者相乘得到 O(n log n) 的稳定复杂度。归并的中间结果必须存放在一个与原数组等长的临时数组里，这也是它空间 O(n) 的来源。
复杂度
- 时间：最好 O(n log n) / 平均 O(n log n) / 最坏 O(n log n) —— 无论输入是否有序都要完整拆分+合并，三档一致
- 空间：O(n)（临时数组 + 递归栈，合计 O(n)）
- 稳定性：稳定 —— 合并时两元素相等用
<=先取左边，相同值的相对顺序不变
图解 1：算法思想与合并不变量
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <vector>
// 合并 a[left..mid] 与 a[mid+1..right] 两个已有序段
template <typename T>
void merge(std::vector<T>& arr, std::vector<T>& tmp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) { // 任何一边先取完后结束循环
// 相等时先取左边，保证稳定
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) { // 剩余部分继续接入 tmp
tmp[k++] = arr[i++];
}
while (j <= right) {
tmp[k++] = arr[j++];
}
for (int p = left; p <= right; ++p) { // tmp 反写回 arr
arr[p] = tmp[p];
}
}
template <typename T>
void mergeSort(std::vector<T>& arr, std::vector<T>& tmp, int left, int right) {
if (left >= right) { // 单个元素已有序
return;
}
int mid = left + (right - left) / 2; // 防溢出
mergeSort(arr, tmp, left, mid); // 左半
mergeSort(arr, tmp, mid + 1, right); // 右半
merge(arr, tmp, left, mid, right); // 合并两个有序段
}要点
- 适用场景：外部排序（数据在磁盘、按块归并）、链表排序（归并是链表排序最优解，无需随机访问、额外空间 O(1)）、求逆序对（在合并过程中顺便统计）。
- 面试加分点：稳定排序 + 三档复杂度都是 O(n log n)，不受输入分布影响，最坏情况也有保证。
- 与快排对比：快排平均 O(n log n) 但最坏 O(n²)、不稳定，胜在常数小且原地排序；归并稳定、最坏有保证，代价是 O(n) 额外空间。
计数排序
原理
计数排序不通过元素间的比较来排序，而是利用值域大小 k 直接「数」出每个值该放的位置。第一步：建一个长度为 k+1 的 count 数组，count[x] 记录值 x 出现的次数。第二步：把 count 原地累加成前缀和，使 count[x] 表示「小于等于 x 的元素个数」，也就是值 x 应占据的最后一个下标加一。第三步：从后往前遍历原数组，每取到 x 就放入 output[--count[x]] 并递减计数，重复元素被依次填入相邻槽位。从后往前配合递减计数，保证了相等元素保持原有相对顺序，因此算法是稳定的。整体不含任何元素比较，当 k 不大时可在 O(n+k) 时间内完成排序。
复杂度
- 时间：最好 O(n+k) / 平均 O(n+k) / 最坏 O(n+k)
- 空间：O(n+k)（count 数组大小 k+1，输出数组大小 n）
- 稳定性：稳定——从后往前放置并递减下标，保证相等元素保持原有相对顺序
图解
图解 1：算法思想与计数语义
图解 2：核心代码逐行执行
C++ 实现
❯C++
#include <vector>
#include <algorithm>
// 计数排序：仅适用于值域较小且为整数的数据
std::vector<int> countingSort(const std::vector<int>& arr) {
if (arr.empty()) return {};
int k = *std::max_element(arr.begin(), arr.end()); // 值域上限
std::vector<int> count(k + 1, 0); // count[x]：值 x 出现次数
// ① 统计频次
for (int x : arr) {
count[x]++;
}
// ② 前缀和：count[i] = 小于等于 i 的元素个数
for (int i = 1; i <= k; ++i) {
count[i] += count[i - 1];
}
// ③ 从后往前放置，--count[x] 保证稳定
std::vector<int> output(arr.size());
for (int i = (int)arr.size() - 1; i >= 0; --i) {
int x = arr[i];
output[--count[x]] = x;
}
return output;
}要点
- 适用场景：值域小且为整数的数据（如成绩 0–100、年龄、字符计数），k 越小优势越明显。
- 局限性：k 很大（如 10⁹）时空间与时间都不可行；非整数（浮点数、字符串）无法直接作为数组下标。
- 与比较排序对比：突破了比较排序 O(n log n) 的下界，但牺牲了通用性，只能用于可整数索引的有限值域。
桶排序
原理
桶排序先把待排序序列按值域划分成若干个有序的桶（区间），再把每个元素根据其数值映射到对应的桶里，这一步只需一遍遍历，是 O(n)。随后对每个桶内的元素单独排序（桶内算法不固定，常用插入排序或 std::sort）。最后把所有桶按区间顺序依次取出元素串联起来，就得到整体有序的结果。它之所以高效，是因为把全局排序拆成多个小规模排序，且在数据近似均匀分布时各桶长度接近、整体趋近线性。桶排序可看作计数排序的推广——计数排序是「一个值一个桶」，而桶排序把值域分成更大的区间。
复杂度
- 时间：最好 O(n+k) / 平均 O(n+k) / 最坏 O(n²)
- 空间：O(n+k)
- 稳定性：稳定（前提桶内用稳定排序）
图解
图解 1：算法思想与分桶不变量
图解 2：映射代码逐行执行
C++ 实现
❯C++
#include <vector>
#include <algorithm>
std::vector<int> bucketSort(const std::vector<int>& arr, int bucket_count = 10) {
if (arr.empty()) {
return {};
}
int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
if (min_val == max_val) return arr;
std::vector<std::vector<int>> buckets(bucket_count); // k 个桶
double range = double(max_val - min_val + 1) / bucket_count; // 每个桶的值域宽度
for (int x : arr) {
int idx = int((x - min_val) / range); // 值 → 桶下标
buckets[idx].push_back(x);
}
std::vector<int> result;
result.reserve(arr.size());
for (auto& b : buckets) {
std::sort(b.begin(), b.end()); // 桶内排序（可用稳定排序替代）
result.insert(result.end(), b.begin(), b.end()); // 按桶顺序串联
}
return result;
}要点
- 适用场景：数据近似均匀分布时接近线性 O(n+k)；数据集中在少数桶时退化为 O(n²)。
- 最坏情况成因：所有元素落入同一个桶，桶内退化为普通排序（如 O(n²) 的插入排序）。
- 与计数排序关系：计数排序是桶排序的特例（每个值一个桶）；桶排序按区间分桶，空间与桶数 k 相关。
基数排序
原理
基数排序不比较元素，而是按关键字的每一位做「分配 + 收集」。以 LSD（Least Significant Digit - 最低有效位）为例：先按个位，把元素依「当前位数字」放入 0–9 号桶（分桶），再按 0→9 的顺序依次取回（收集）；下一趟按十位重复，再百位，直到最高位。由于每趟收集都保持桶内元素的原有相对顺序（稳定），低位已排好的结果会被高位正确继承，最终整体有序。核心操作是「按位分桶 + 稳定收集」的循环，子程序通常用计数排序实现。
复杂度
- 时间：最好 O(nk) / 平均 O(nk) / 最坏 O(nk)
- 空间：O(n+k)
- 稳定性：稳定（每趟分桶/收集保持桶内元素原有先后顺序，不会打乱已排好的低位）
图解
图解 1：算法思想与逐位不变量
图解 2：按位计数逐行执行
C++ 实现
❯C++
#include <vector>
#include <algorithm> // std::max_element
// 稳定子程序：按 exp 位做一次计数排序
void countingSortByDigit(std::vector<int>& arr, int exp) {
const int n = static_cast<int>(arr.size());
std::vector<int> output(n);
int count[10] = {0};
for (int x : arr) { // 统计当前位出现次数
++count[(x / exp) % 10];
}
for (int i = 1; i < 10; ++i) { // 前缀和 → 稳定落点
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; --i) { // 从后往前，保证稳定
output[--count[(arr[i] / exp) % 10]] = arr[i];
}
arr = output;
}
void radixSort(std::vector<int>& arr) {
if (arr.empty()) {
return;
}
int maxVal = *std::max_element(arr.begin(), arr.end());
// LSD：exp = 1, 10, 100, ... 逐位稳定排序
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}要点
- 适用场景：非负整数，或定长关键字（等长字符串按字符、日期按位）——关键字位数 k 越短越划算。
- 与计数排序的关系：每一趟就是一次「按某一位」的计数排序，故可看作对每位做多趟稳定计数排序。
- 局限：需额外空间 O(n+k)；依赖「按位可分割」的关键字，不直接适用浮点/任意比较；常数因子较大，n 小时不如快排。
整体调用代码
❯C++
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
void printVector(const std::vector<int>& vec, const std::string& prefix = "") {
if (!prefix.empty()) {
std::cout << prefix;
}
for (const auto i : vec) {
std::cout << i << " ";
}
std::cout << std::endl;
}
/**
这里放实际的算法代码
**/
template <typename T>
using SortFun = std::function<void(std::vector<T>&)>;
template <typename T>
struct NamedSort {
std::string name;
SortFun<T> fn;
};
template <typename T>
void processSort(std::vector<T>& vec, SortFun<T> sorter, const std::string& sortName = "", bool is_shuffle = true) {
if (is_shuffle) {
std::shuffle(vec.begin(), vec.end(), std::mt19937{std::random_device{}()});
}
printVector(vec, "Before sorting" + (sortName.empty() ? "" : " " + sortName) + ": ");
sorter(vec);
printVector(vec, "After sorting" + (sortName.empty() ? "" : " " + sortName) + ": ");
}
int main() {
std::vector<int> v(10);
std::iota(v.begin(), v.end(), 1); // 初始化为 1 到 10
std::vector<NamedSort<int>> sorters = {
{"bubbleSort", bubbleSort<int>},
{"selectionSort", selectionSort<int>},
{"insertionSort", insertionSort<int>},
{"shellSort", shellSort<int>},
{"quickSort", [](std::vector<int>& vec) { quickSort(vec, 0, static_cast<int>(vec.size()) - 1); }},
{"heapSort", heapSort<int>},
{"mergeSort", [](std::vector<int>& vec) {
std::vector<int> tmp(vec.size());
mergeSort(vec, tmp, 0, static_cast<int>(vec.size()) - 1);
}}};
for (const auto& sorter : sorters) {
processSort(v, sorter.fn, sorter.name);
}
std::vector<int> counting_input = {5, 1, 5, 3, 5, 2, 1, 5, 0, 3, 2, 5};
processSort<int>(counting_input, [](std::vector<int>& vec) { vec = countingSort(vec); }, "countingSort", false);
std::vector<int> bucket_input = {42, 5, 73, 19, 88, 34, 61, 27, 95, 12, 56, 44, 67, 31, 80,
23, 49, 70, 2, 99, 15, 38, 52, 64, 77, 90, 11, 29, 47, 58};
processSort<int>(bucket_input, [](std::vector<int>& vec) { vec = bucketSort(vec); }, "bucketSort", false);
std::vector<int> radix_input = {170, 45, 75, 90, 802, 24, 2, 66, 5, 500,
1000, 999, 12, 120, 121, 0, 45, 802, 7, 77};
processSort<int>(radix_input, radixSort, "radixSort", false);
return 0;
}