排序
8.1 排序的基本概念
排序是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。
相关概念：
- 稳定性：两个相等关键字的元素在排序前后相对位置不变，则排序算法是稳定的。
- 内部排序：待排序记录全部存放在内存中进行的排序。
- 外部排序：待排序记录数量太大，需要借助外存进行的排序。
💡 记忆技巧：稳定性可以理解为"保持原样"——相等的元素在排序后谁前谁后，和排序前一样。
8.2 插入排序
直接插入排序
将待排序元素插入到已有序序列的合适位置。
void InsertSort(int a[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
if (a[i] < a[i-1]) {
temp = a[i];
for (j = i-1; j >= 0 && a[j] > temp; j--)
a[j+1] = a[j];
a[j+1] = temp;
}
}
}
| 指标 | 值 |
|---|---|
| 最好时间复杂度 | O(n)（已有序） |
| 最坏时间复杂度 | O(n²)（逆序） |
| 平均时间复杂度 | O(n²) |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
折半插入排序
用折半查找替代直接插入中的顺序查找，减少比较次数。
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n²)（移动次数不变） |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
⚠️ 易错点：折半插入排序虽然减少了比较次数，但移动次数不变，所以时间复杂度仍然是 O(n²)。
希尔排序
将序列分成若干子序列分别进行插入排序，最后进行一次"全序列插入排序"。
void ShellSort(int a[], int n) {
int i, j, temp, dk;
for (dk = n/2; dk >= 1; dk = dk/2) {
for (i = dk; i < n; i++) {
if (a[i] < a[i-dk]) {
temp = a[i];
for (j = i-dk; j >= 0 && a[j] > temp; j -= dk)
a[j+dk] = a[j];
a[j+dk] = temp;
}
}
}
}
| 指标 | 值 |
|---|---|
| 时间复杂度 | 依赖于增量序列，最坏 O(n²)，最好约 O(n^1.3) |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
8.3 交换排序
冒泡排序
相邻元素两两比较，逆序则交换。每一轮将最大元素"冒泡"到最后。
void BubbleSort(int a[], int n) {
for (int i = 0; i < n-1; i++) {
bool flag = false;
for (int j = 0; j < n-1-i; j++) {
if (a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = true;
}
}
if (!flag) break; // 没有交换，说明已经有序
}
}
| 指标 | 值 |
|---|---|
| 最好时间复杂度 | O(n)（已有序，加了flag优化） |
| 最坏时间复杂度 | O(n²) |
| 平均时间复杂度 | O(n²) |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
快速排序（重点）
基于分治思想。选一个基准元素（pivot），将比基准小的放在左边，比基准大的放在右边，然后递归处理左右子序列。
int Partition(int a[], int low, int high) {
int pivot = a[low];
while (low < high) {
while (low < high && a[high] >= pivot) high--;
a[low] = a[high];
while (low < high && a[low] <= pivot) low++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
void QuickSort(int a[], int low, int high) {
if (low < high) {
int pivotpos = Partition(a, low, high);
QuickSort(a, low, pivotpos - 1);
QuickSort(a, pivotpos + 1, high);
}
}
| 指标 | 值 |
|---|---|
| 最好时间复杂度 | O(n log n) |
| 最坏时间复杂度 | O(n²)（每次选的基准都是最值） |
| 平均时间复杂度 | O(n log n) |
| 空间复杂度 | O(log n)（递归栈深度） |
| 稳定性 | 不稳定 |
优化方法：
- 三数取中法选取基准。
- 随机选取基准。
- 当子序列长度较小时改用插入排序。
💡 记忆技巧：快排的过程可以理解为一个"挖坑填数"游戏——选一个基准挖个坑，从右边找小的填到左边（挖了新坑），再从左边找大的填到右边（又挖了新坑），最后把基准填到最后一个坑。
📌 408考点提示：快速排序的每一趟划分结果是高频考点。需要能手动模拟每一趟的划分过程，写出每一趟后的序列。
8.4 选择排序
简单选择排序
每轮选择最小元素放到前面。
void SelectSort(int a[], int n) {
for (int i = 0; i < n-1; i++) {
int min = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[min]) min = j;
if (min != i) {
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n²)（任何情况） |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
堆排序（重点）
利用堆（完全二叉树）的特性进行排序。堆分为大根堆（根最大）和小根堆（根最小）。
建堆：从最后一个非叶子结点开始，向下调整。
void HeadAdjust(int a[], int k, int len) {
int temp = a[k];
for (int i = 2*k; i <= len; i *= 2) {
if (i < len && a[i] < a[i+1]) i++;
if (temp >= a[i]) break;
a[k] = a[i];
k = i;
}
a[k] = temp;
}
void BuildMaxHeap(int a[], int len) {
for (int i = len/2; i > 0; i--)
HeadAdjust(a, i, len);
}
堆排序：建堆后，将堆顶元素与堆底交换，堆大小减 1，然后调整堆顶。
void HeapSort(int a[], int n) {
BuildMaxHeap(a, n);
for (int i = n; i > 1; i--) {
int temp = a[1];
a[1] = a[i];
a[i] = temp;
HeadAdjust(a, 1, i-1);
}
}
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n)（任何情况） |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
⚠️ 易错点：堆排序的堆顶元素与最后一个元素交换后，堆的大小减 1，然后对新的堆顶执行向下调整（不是建堆！）。建堆只做一次，在排序开始前。
8.5 归并排序
二路归并将两个有序序列合并为一个有序序列。
void Merge(int a[], int low, int mid, int high) {
int *b = (int*)malloc((high-low+1)*sizeof(int));
for (int k = low; k <= high; k++) b[k] = a[k];
int i = low, j = mid+1, k = low;
while (i <= mid && j <= high) {
if (b[i] <= b[j]) a[k++] = b[i++];
else a[k++] = b[j++];
}
while (i <= mid) a[k++] = b[i++];
while (j <= high) a[k++] = b[j++];
free(b);
}
void MergeSort(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}
}
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n)（任何情况） |
| 空间复杂度 | O(n) |
| 稳定性 | 稳定 |
8.6 基数排序
基数排序按"位"进行排序，从最低位到最高位依次排序（LSD），或从最高位到最低位（MSD）。
- 需要每个关键字有固定的位数（长度不一致补 0）。
- 每一趟用"分配"和"收集"完成。
- 需要 r 个队列（r 为基数，如十进制就是 10 个队列）。
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(d(n+r))，d 为位数，r 为基数 |
| 空间复杂度 | O(r) |
| 稳定性 | 稳定 |
8.7 各种排序算法比较
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 折半插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | — | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | 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(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 |
💡 记忆技巧："快些选堆"（快排、希尔、选择、堆排）都是不稳定的。其他常见的内部排序（插入、冒泡、归并、基数、折半插入）都是稳定的。
8.8 外部排序
基本概念
外部排序通常采用多路归并方法：
- 生成初始归并段（用内部排序）。
- 多路归并：将多个归并段合并为一个有序段。
多路归并与败者树
使用败者树（一种选择树）可以优化 k 路归并中找最小值的过程，每次比较次数从 k-1 减少到 log₂k。
k 路归并的趟数：S = ⌈logₖ(m)⌉，m 是初始归并段数量。 总时间 = 生成归并段时间 + 读写时间 + 归并时间。
置换-选择排序
生成比内存容量更大的初始归并段。利用工作区 + 输入缓冲区，从待排文件中不断读入记录，生成尽可能大的归并段。
最佳归并树
类似哈夫曼树，归并树的带权路径长度之和（I/O 次数）最小。
- k 路归并的最佳归并树是所有叶子结点的带权路径长度最小的 k 叉树。
- 若 (m-1) % (k-1) ≠ 0，需要补 0 权值虚段。
本章总结
排序是 408 的重点章节，快速排序和堆排序是最常出现在综合题中的算法。需要掌握每种排序的过程（能手算模拟每一趟的结果）、时间/空间复杂度、稳定性。在外部排序中，多路归并的趟数计算和最佳归并树的构造也是常见题型。