Sort
排序是所有算法的前置步骤
排序本身很少是目的,更多是手段——排完序之后:
- 二分查找成为可能
- 双指针成为可能
- 贪心策略有了明确的顺序
- 相同元素聚在一起(去重、计数)
**"先排序再说"**是解题时最常用的一步。
比较排序
总览
| 算法 | 平均 | 最坏 | 最好 | 空间 | 稳定 | 原地 |
|---|---|---|---|---|---|---|
| 冒泡排序 | ✓ | ✓ | ||||
| 选择排序 | ✗ | ✓ | ||||
| 插入排序 | ✓ | ✓ | ||||
| 希尔排序 | ✗ | ✓ | ||||
| 归并排序 | ✓ | ✗ | ||||
| 快速排序 | ✗ | ✓ | ||||
| 堆排序 | ✗ | ✓ | ||||
| 计数排序 | ✓ | ✗ | ||||
| 基数排序 | — | — | ✓ | ✗ | ||
| 桶排序 | — | ✓ | ✗ |
冒泡排序
反复交换相邻逆序对,每轮把最大的"浮"到末尾。
void bubble_sort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 已有序,提前退出
}
}唯一价值:教学。swapped 优化让最好情况(已有序)是。实际不用。
选择排序
每轮找未排序部分的最小值,放到当前位置。
void selection_sort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int mn = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[mn]) mn = j;
swap(a[i], a[mn]);
}
}不稳定:swap 会把前面的元素换到后面。例:[2a, 2b, 1] → 第一轮 [1, 2b, 2a],两个 2 的相对顺序变了。
特点:比较次数固定,但交换次数只有——交换代价高的场景有价值(罕见)。
插入排序
把每个元素插到前面已排序部分的正确位置。
void insertion_sort(vector<int>& a) {
for (int i = 1; i < (int)a.size(); i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // 后移,不是交换
j--;
}
a[j + 1] = key;
}
}稳定:a[j] > key 而不是 >=,相等时不移动。
实际很重要:
- 小规模()时比快排快(常数小、无递归、缓存友好)
- 近乎有序的数据上是
- 所以所有工业级排序在小数组上都退化成插入排序(
std::sort在 时用插入排序)
希尔排序
分组插入排序,间隔逐步缩小。
void shell_sort(vector<int>& a) {
int n = a.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = a[i], j = i;
while (j >= gap && a[j - gap] > key) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = key;
}
}
}优势: 空间、原地、代码短,平均。嵌入式或内存受限场景有用。
归并排序
见分治章节。核心是合并两个有序段。
- 唯一稳定的 比较排序(无需额外分配的稳定排序)
- 缺点:需要 辅助空间
- 外部排序的主力:数据放不下内存时,归并是唯一可行(只需顺序读)
快速排序
int partition(vector<int>& a, int l, int r) {
int pivot = a[r];
int i = l;
for (int j = l; j < r; j++)
if (a[j] < pivot) swap(a[i++], a[j]);
swap(a[i], r);
return i;
}
void quick_sort(vector<int>& a, int l, int r) {
if (l >= r) return;
int p = partition(a, l, r);
quick_sort(a, l, p - 1);
quick_sort(a, p + 1, r);
}性能关键在 pivot 选择:
| 策略 | 最坏场景 | 效果 |
|---|---|---|
总选 a[r] | 已排序数组 → | 差 |
| 随机选 | 随机数据好,可被构造卡 | 中 |
| 三数取中(median-of-three) | 常见有序模式 OK | 好 |
| 取真正的中位数 | 不可能(代价高) | — |
优化:
- 小区间用插入排序()
- 三数取中选 pivot
- 尾递归消除:先递归小的那半,大的那半用循环(保证栈深)
- 三路划分(处理大量重复元素,见下)
三路划分(处理重复元素)
// 数组分成 [< pivot][== pivot][> pivot] 三段
void quick_sort3(vector<int>& a, int l, int r) {
if (l >= r) return;
int pivot = a[l + (r - l) / 2];
int i = l, j = l, k = r;
while (j <= k) {
if (a[j] < pivot) swap(a[i++], a[j++]);
else if (a[j] > pivot) swap(a[j], a[k--]);
else j++;
}
quick_sort3(a, l, i - 1);
quick_sort3(a, k + 1, r);
}价值:全是相同元素时,普通快排是(每次只减少 1),三路划分是。
堆排序
void sift_down(vector<int>& a, int i, int n) {
while (true) {
int l = 2 * i + 1, r = l + 1, mx = i;
if (l < n && a[l] > a[mx]) mx = l;
if (r < n && a[r] > a[mx]) mx = r;
if (mx == i) break;
swap(a[i], a[mx]);
i = mx;
}
}
void heap_sort(vector<int>& a) {
int n = a.size();
for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n); // 建堆 O(n)
for (int i = n - 1; i > 0; i--) {
swap(a[0], a[i]); // 最大元素换到末尾
sift_down(a, 0, i); // 恢复堆
}
}- 原地、 额外空间、最坏
- 不稳定、缓存不友好(跳跃访问)
- 建堆是 不是——因为大部分节点在底层,下沉距离短
为什么实际不如快排:缓存局部性差。但在要求最坏保证和只需前 k 个的场景有用。
非比较排序
计数排序
元素值域小()时,统计每个值出现次数。
void counting_sort(vector<int>& a, int k) {
vector<int> cnt(k + 1, 0);
for (int x : a) cnt[x]++;
for (int i = 1; i <= k; i++) cnt[i] += cnt[i - 1]; // 前缀和 → 每个值的最终位置
vector<int> out(a.size());
for (int i = (int)a.size() - 1; i >= 0; i--) // 从后往前保证稳定
out[--cnt[a[i]]] = a[i];
a = out;
},突破 下界——因为它不基于比较,用了"值是小整数"这个额外信息。
为什么从后往前遍历:保证稳定性(先处理后面的,相同元素保持原相对顺序)。
基数排序
按位(个位 → 十位 → 百位…)分别做稳定的计数排序。
void radix_sort(vector<int>& a) {
const int B = 1 << 8; // 每 8 位一轮
int n = a.size();
vector<int> tmp(n);
for (int shift = 0; shift < 32; shift += 8) {
vector<int> cnt(B + 1, 0);
for (int x : a) cnt[((x >> shift) & (B - 1)) + 1]++;
for (int i = 1; i <= B; i++) cnt[i] += cnt[i - 1];
for (int x : a) tmp[cnt[(x >> shift) & (B - 1)]++] = x;
a.swap(tmp);
}
}, 是位数/轮数。对 32 位整数、8 位一轮 → 4 轮。
特点:
- 比快排快(当 大且值域小时)
- 稳定
- 需要额外空间
注意负数:要特殊处理(加偏移或先分离正负)。
桶排序
把值域分成若干桶,桶内排序,再串联。
- 数据均匀分布时
- 最坏(全落一个桶)退化到桶内算法的复杂度
比较排序的下界
任何基于比较的排序,最坏至少 次比较。
证明(决策树):
n 个元素有 n! 种排列
每次比较最多把可能性分成 2 份
决策树需要至少 n! 个叶子
树高 h 满足 2^h >= n!
→ h >= log2(n!) = Ω(n log n) (Stirling 公式)推论:
- 归并、快排、堆排序在渐近意义下已经最优
- 要更快必须不基于比较(计数、基数、桶)
C++ 标准库
#include <algorithm>
// 1. sort:内省排序(Introsort)
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
sort(v.begin(), v.end(), [](const Item& a, const Item& b) {
if (a.x != b.x) return a.x < b.x; // 多关键字:先比 x
return a.y < b.y; // 再比 y
});
// 2. stable_sort:稳定(归并),O(n log n),必要时 O(n log^2 n)
stable_sort(v.begin(), v.end());
// 3. partial_sort:只保证前 k 个有序,O(n log k)
partial_sort(v.begin(), v.begin() + k, v.end());
// 4. nth_element:保证第 n 个位置是"如果全排序会在那的元素",O(n) 平均
nth_element(v.begin(), v.begin() + n / 2, v.end()); // 求中位数用这个
int median = v[n / 2];
// 5. 有序性检查
bool ok = is_sorted(v.begin(), v.end());std::sort 的实现(Introsort):
1. 快排(三数取中 pivot)
2. 递归深度超过 2*log(n) → 切换到堆排序(防止快排退化到 O(n^2))
3. 子数组 <= 16 → 插入排序这是工业级排序的标准答案:结合了三种算法各自的优点。
比较函数的要求
必须是严格弱序(strict weak ordering):
// 要求:
comp(a, a) == false // 非自反
comp(a, b) && comp(b, a) 不能同时为真 // 非对称
comp(a,b) && comp(b,c) ⇒ comp(a,c) // 传递
// 错误示范(会导致 UB,可能崩溃)
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; }); // 错!a==b 时返回 true经典 bug:用 <= 而不是 <。这会让 comp(a,a) == true,破坏严格弱序,导致越界访问。
排序作为其他算法的工具
| 用途 | 做法 |
|---|---|
| 去重 | 排序后相邻比较,unique |
| 计数 | 排序后统计连续段长度 |
| 双指针 | 排序后两数之和、区间问题 |
| 二分 | 排序后才能二分 |
| 贪心 | 排序确定处理顺序 |
| 离散化 | 排序 + 去重 + 二分映射 |
| 扫描线 | 按坐标排序,依次处理事件 |
离散化(常用模板)
vector<int> xs = a; // 复制
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 去重
// 值 x 映射到的下标(0-based)
int id = lower_bound(xs.begin(), xs.end(), x) - xs.begin();用途:值域很大()但元素个数少()时,压缩到 以便用数组/树状数组。
常见坑
- 比较函数用
<=:破坏严格弱序,UB - 排序后忘了去重就二分:重复元素不影响二分正确性,但计数会错
- 结构体排序的比较函数漏了某个关键字:导致不稳定行为
nth_element不保证前 k 个有序:只保证第 n 个位置正确且左边的都不大于它- 基数排序处理负数:需要先偏移
- 以为
sort是稳定的:不是。要稳定用stable_sort或在比较函数里加"原下标"作为最后的关键字 - 对大对象排序的拷贝开销:用指针/索引排序,或给结构体实现移动语义
- 排序键为浮点:避免直接比较相等,用 eps
- 稳定排序的意义:多关键字排序时,可以按次要关键字先排一次,再用稳定排序排主关键字