排序算法分类
排序算法按比较方式分为比较排序（冒泡、选择、插入、归并、快排、堆排，理论下界 O(n log n)）和非比较排序（计数、基数、桶排序，可以突破 O(n log n)）；按稳定性分为稳定排序（相等元素相对顺序不变）和不稳定排序。
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 l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l+i];
for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
快速排序（不稳定）
选基准（pivot）分区：小的在左、大的在右，再递归两边。平均 O(n log n)，最坏 O(n²)（已有序 + 固定取尾元素为基准时）；空间 O(log 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)）
统计每个值的出现次数，前缀和得到”排名”，倒序放回保证稳定。适合整数且值域不大的场景。
基数排序（稳定，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：切到插入排序（小数据常数小）。
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；内存敏感手写堆排；整数小值域用计数/基数排序。