排序算法分类
排序算法按比较方式分两类：比较排序（冒泡、选择、插入、归并、快排、堆排）理论下界是 O(n log n)——任何基于两两比较的排序都不可能更快；非比较排序（计数、基数、桶）利用数据本身的特征，可以突破这个下界。
另一个关键维度是稳定性：稳定排序保证相等元素的相对顺序不变。只有当”先按 A 排、再按 B 排，希望 A 的相对顺序保留”时才有意义（比如先按时间后按优先级）。
O(n²) 基础排序
冒泡排序（稳定）
相邻元素两两比较，一趟把最大值”冒”到末尾。优化点：某趟无交换说明已有序，提前结束。
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 已有序，提前退出
}
}
选择排序（不稳定）
每趟在未排序部分找最小元素，放到已排序末尾。比较次数固定 O(n²)，交换最多 n 次——交换代价昂贵的场景它比冒泡好。
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
插入排序（稳定）
把当前元素插入到前面已排序部分的正确位置。对基本有序的数据非常快（最优 O(n)），是快排在小规模数据时的收尾选择。
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
O(n log n) 高级排序
归并排序（稳定）
分治：先拆到单元素，再两两有序合并。稳定、最坏也是 O(n log n)，代价是需要 O(n) 额外空间。
void merge(int arr[], int low, int mid, int high) {
vector<int> tmp(high - low + 1);
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high)
tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while (i <= mid) tmp[k++] = arr[i++];
while (j <= high) tmp[k++] = arr[j++];
copy(tmp.begin(), tmp.end(), arr + low);
}
void mergeSort(int arr[], int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
快速排序（不稳定）
选基准、分区、递归。平均 O(n log n)、原地（O(log n) 栈空间）、常数小，是通用排序的事实标准；最坏 O(n²) 出现在基准选取恰好最差时（如已有序数据 + 固定取末尾）。
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 基准取末尾
int i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] < pivot)
swap(arr[++i], arr[j]);
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
最坏情况规避：随机选基准、三数取中，或直接用下面讲的 Introsort。
堆排序（不稳定）
建大顶堆后反复把堆顶换到末尾并下沉。O(n log n) 且原地（O(1) 额外空间），但常数较大、缓存不友好——实际场景很少主动用它。
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 建堆 O(n)
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
非比较排序
计数排序（稳定，O(n+k)）
统计每个值的出现次数，前缀和得到”排名”，倒序放回保证稳定。适合整数且值域不大的场景。
// 值域 [0, k)，O(n + k)
void countingSort(int arr[], int n, int k) {
vector<int> cnt(k, 0), out(n);
for (int i = 0; i < n; i++) cnt[arr[i]]++;
for (int i = 1; i < k; i++) cnt[i] += cnt[i - 1]; // 前缀和 → 排名
for (int i = n - 1; i >= 0; i--) { // 倒序放回，保证稳定
out[--cnt[arr[i]]] = arr[i];
}
copy(out.begin(), out.end(), arr);
}
基数排序（稳定，O(n·k)）
按位从低位到高位做多轮计数排序，k 为最大位数。适合整数/定长字符串。每轮稳定是关键——后一轮按高位排时不会破坏低位的相对顺序。
对比总表
| 算法 | 平均 | 最坏 | 空间 | 稳定 | 适用 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✅ | 教学/小规模 |
| 选择 | O(n²) | O(n²) | O(1) | ❌ | 小规模 |
| 插入 | O(n²) | O(n²) | O(1) | ✅ | 基本有序/小规模 |
| 归并 | O(n log n) | O(n log n) | O(n) | ✅ | 大规模且需稳定 |
| 快排 | O(n log n) | O(n²) | O(log n) | ❌ | 大规模通用 |
| 堆排 | O(n log n) | O(n log n) | O(1) | ❌ | 空间受限 |
| 计数 | O(n+k) | O(n+k) | O(n+k) | ✅ | 整数小值域 |
| 基数 | O(nk) | O(nk) | O(n+k) | ✅ | 整数位数少 |
工程实现：STL 的 Introsort
C++ 的 std::sort 默认实现是内省排序（Introsort），混合三种算法：
- 递归深度 < 2·log₂n：用快排（平均最优）；
- 递归深度超过阈值：切到堆排序，杜绝最坏 O(n²)；
- 数据规模 ≤ 16–32：切到插入排序（小数据常数小）。
#include <algorithm>
std::sort(v.begin(), v.end()); // 升序（不稳定）
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序
std::stable_sort(v.begin(), v.end()); // 稳定排序（归并）
std::partial_sort(v.begin(), v.begin() + 3, v.end());// 只排序前 3 个
选型建议：通用排序用 std::sort（Introsort）；需要稳定用 std::stable_sort；内存敏感手写堆排；整数小值域用计数/基数排序。