数据结构 —— 排序（Sort）完整教程
面向考试 / 期末考试，涵盖排序章节全部核心知识点
目录
1. 基本概念
1.1 排序的定义
将一组无序的记录序列调整为按关键字有序的序列。
1.2 排序的分类
| 分类维度 | 类型 |
|---|---|
| 稳定性 | 稳定排序 / 不稳定排序 |
| 存储介质 | 内部排序（内存）/ 外部排序（外存） |
| 基本操作 | 比较类 / 非比较类（基数排序） |
1.3 稳定性 ★
稳定排序：相同关键字的记录在排序后相对位置不变。
| 稳定的排序 | 不稳定的排序 |
|---|---|
| 直接插入、冒泡、归并、基数 | 希尔、简单选择、快速、堆 |
记忆口诀：不稳定的——“希尔快选堆”（希尔排序、快速排序、选择排序、堆排序）
2. 插入排序
2.1 直接插入排序
思想：将待排序记录逐个插入到已排好序的序列中。
类似于打牌时摸牌、插牌的过程。
初始： [5] 2 8 1 9第1趟： [2 5] 8 1 9 ← 2 插入到 5 前面第2趟： [2 5 8] 1 9 ← 8 比 5 大，在末尾第3趟： [1 2 5 8] 9 ← 1 插入到最前面第4趟： [1 2 5 8 9] ← 9 比 8 大，在末尾算法实现（C 语言）：
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]; // 大于 temp 的元素后移 a[j+1] = temp; // 插入到正确位置 } }}性能分析：
| 指标 | 最好情况（正序） | 最坏情况（逆序） | 平均情况 |
|---|---|---|---|
| 比较次数 | $n-1$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| 移动次数 | $0$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| 时间复杂度 | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| 空间复杂度 | $O(1)$ | $O(1)$ | $O(1)$ |
关键性质：
- 稳定排序 ✓
- 适合基本有序的数据，效率接近 $O(n)$
- 也适合数据量小的情况
2.2 折半插入排序
在查找插入位置时使用折半查找（二分查找），减少比较次数，但移动次数不变。
void BinaryInsertSort(int a[], int n) { int i, j, low, high, mid, temp; for (i = 1; i < n; i++) { temp = a[i]; low = 0; high = i - 1; // 折半查找插入位置 while (low <= high) { mid = (low + high) / 2; if (a[mid] > temp) high = mid - 1; else low = mid + 1; } // 移动元素 for (j = i - 1; j >= low; j--) a[j+1] = a[j]; a[low] = temp; }}| 对比 | 直接插入 | 折半插入 |
|---|---|---|
| 比较次数 | $O(n^2)$ | $O(n\log n)$ |
| 移动次数 | $O(n^2)$ | $O(n^2)$（不变） |
| 时间复杂度 | $O(n^2)$ | $O(n^2)$（仍为 $O(n^2)$） |
3. 希尔排序
希尔排序 = 插入排序 + 增量分组。本质上是插入排序的改进！
3.1 核心思想 ★
直接插入排序在基本有序时效率高（$O(n)$），在数据量小时也高效。
希尔排序利用这两点：
- 将序列分成若干增量间隔的子序列
- 对每个子序列进行直接插入排序
- 不断缩小增量，直到增量为 1（此时就是普通的直接插入排序，但数据已基本有序）
3.2 过程示意
原序列： 49 38 65 97 76 13 27 49 55 04增量 d=5（每隔5个一组）： 49 ─────────── 13 → [13, 49] 38 ─────────── 27 → [27, 38] 65 ─────────── 49 → [49, 65] 97 ─────────── 55 → [55, 97] 76 ─────────── 04 → [04, 76]结果： 13 27 49 55 04 49 38 65 97 76
增量 d=3（每隔3个一组）： 13 ───── 55 ───── 38 ───── 76 → [13, 38, 55, 76] 27 ───── 04 ───── 65 → [04, 27, 65] 49 ───── 49 ───── 97 → [49, 49, 97]结果： 13 04 49 38 27 49 55 65 97 76
增量 d=1（普通插入排序）： （此时序列已基本有序，插入排序效率极高）结果： 04 13 27 38 49 49 55 65 76 973.3 算法实现（C 语言）
void ShellSort(int a[], int n) { int d, i, j, temp; // 增量序列：每次除以 2 for (d = n / 2; d >= 1; d /= 2) { // 对每个子序列做直接插入排序 for (i = d; i < n; i++) { if (a[i] < a[i-d]) { temp = a[i]; for (j = i - d; j >= 0 && a[j] > temp; j -= d) a[j+d] = a[j]; a[j+d] = temp; } } }}3.4 增量序列
| 增量序列 | 公式 | 最坏时间复杂度 |
|---|---|---|
| Shell 原始 | $d_k = \lfloor n/2^k \rfloor$ | $O(n^2)$ |
| Hibbard | $d_k = 2^k - 1$（1, 3, 7, 15…） | $O(n^{1.5})$ |
| Sedgewick | 1, 5, 19, 41, 109… | $O(n^{4/3})$ |
考试一般用 Shell 原始增量（每次折半）。
3.5 性质
| 性质 | 值 |
|---|---|
| 时间复杂度 | 约 $O(n^{1.3}) \sim O(n^2)$，依赖于增量序列 |
| 空间复杂度 | $O(1)$ |
| 稳定性 | 不稳定（相同关键字可能被分到不同子序列） |
3.6 希尔排序 vs 插入排序
| 插入排序 | 希尔排序 | |
|---|---|---|
| 基本操作 | 逐个比较移动 | 跳跃式比较移动 |
| 初始有序性 | 无要求 | 利用逐步有序 |
| 稳定性 | 稳定 | 不稳定 |
| 效率 | $O(n^2)$ | 约 $O(n^{1.3})$ |
结论：希尔排序是插入排序在大数据量下的改进版本，用小增量的多次排序换取整体效率提升。
4. 冒泡排序
4.1 基本思想
从后往前（或从前往后）两两比较相邻元素，若逆序则交换，每一趟确定一个最值的位置。
原序列： 49 38 65 97 76 13 27 49
第1趟：（从后往前冒） 49↔38 → 38 49 65 97 76 13 27 49 （38冒到最前面） 结果：[13] 38 49 65 97 76 27 49 ← 13 确定
第2趟： 结果：[13 27] 38 49 65 97 76 49 ← 27 确定
...最终：[13 27 38 49 49 65 76 97]4.2 算法实现（C 语言）
void BubbleSort(int a[], int n) { int i, j, temp; int flag; // 标记本趟是否发生交换 for (i = 0; i < n - 1; i++) { flag = 0; for (j = n - 1; j > i; j--) { if (a[j-1] > a[j]) { // 逆序则交换 temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; flag = 1; } } if (flag == 0) // 没有交换 → 已经有序 break; }}4.3 性能分析
| 指标 | 最好（正序） | 最坏（逆序） | 平均 |
|---|---|---|---|
| 比较次数 | $n-1$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| 交换次数 | $0$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| 时间复杂度 | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| 空间复杂度 | $O(1)$ |
- 稳定排序 ✓（相同值不会交换）
5. 快速排序 ★★★
基于分治法，是内部排序中平均性能最优的算法。
5.1 基本思想
- 从序列中选一个元素作为枢轴（pivot）
- 划分：将序列分为两部分——左边全部 ≤ pivot，右边全部 ≥ pivot
- 递归地对左右两部分排序
原序列： 49 38 65 97 76 13 27 49 ↑ pivot=49
一趟划分后： [27 38 13] 49 [76 97 65 49] 左边 ≤ 49 右边 ≥ 49
递归对左右排序...最终：[13 27 38 49 49 65 76 97]5.2 一趟划分（核心操作）
int Partition(int a[], int low, int high) { int pivot = a[low]; // 选第一个元素为枢轴 while (low < high) { // high 向左找比 pivot 小的 while (low < high && a[high] >= pivot) high--; a[low] = a[high]; // 将此小的移到左边
// low 向右找比 pivot 大的 while (low < high && a[low] <= pivot) low++; a[high] = a[low]; // 将此大的移到右边 } a[low] = pivot; // 枢轴归位 return low; // 返回枢轴位置}5.3 递归实现
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); // 递归右半部分 }}5.4 性能分析
| 指标 | 最好 | 最坏 | 平均 |
|---|---|---|---|
| 时间复杂度 | $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ |
| 空间复杂度 | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
| 稳定性 | 不稳定 |
- 最好/平均情况：每次枢轴恰好将序列均分，递归树高度 $\log n$
- 最坏情况：序列正序或逆序，每次划分出一边为空，退化为 $O(n^2)$
- 空间复杂度来源于递归工作栈
5.5 优化方法
- 三数取中：选
low, mid, high三个位置的中位数做枢轴 - 随机选取枢轴
- 小规模时切换到插入排序
6. 简单选择排序
6.1 基本思想
每一趟从待排序元素中选出**最小（或最大）**的一个，放到已排序序列末尾。
原序列： 49 38 65 97 76 13 27 49
第1趟：在 [49 38 65 97 76 13 27 49] 中找最小 → 13，与 49 交换 [13] 38 65 97 76 49 27 49
第2趟：在 [38 65 97 76 49 27 49] 中找最小 → 27，与 38 交换 [13 27] 65 97 76 49 38 49
第3趟：在 [65 97 76 49 38 49] 中找最小 → 38，与 65 交换 [13 27 38] 97 76 49 65 49
...最终：[13 27 38 49 49 65 76 97]6.2 算法实现（C 语言）
void SelectSort(int a[], int n) { int i, j, min, temp; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) { temp = a[i]; a[i] = a[min]; a[min] = temp; } }}6.3 性能分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | $O(n^2)$（与初始序列无关） |
| 比较次数 | $\frac{n(n-1)}{2}$（固定） |
| 交换次数 | $0 \sim n-1$ |
| 空间复杂度 | $O(1)$ |
| 稳定性 | 不稳定（交换可能破坏相对顺序） |
比如
[5, 5, 2]，第 1 趟把 2 和第一个 5 交换，两个 5 的相对位置就变了。
7. 堆排序
7.1 堆的定义 ★
大根堆：每个结点的值 ≥ 其左右孩子的值（a[i] ≥ a[2i+1] 且 a[i] ≥ a[2i+2]）
小根堆：每个结点的值 ≤ 其左右孩子的值
大根堆示例： 97 / \ 76 65 / \ / \ 49 38 13 27
数组存储：[97, 76, 65, 49, 38, 13, 27]7.2 核心操作
堆排序 = 建堆 + 反复输出堆顶 + 调整堆
7.3 堆调整（核心）
// 将 a[k] 为根的子树调整为大根堆// n 是堆的大小void HeapAdjust(int a[], int k, int n) { int root = a[k]; // 暂存根结点 int i; for (i = 2 * k + 1; i < n; i = 2 * i + 1) { // i 指向左孩子 // 选左右孩子中较大的 if (i + 1 < n && a[i] < a[i+1]) i++; // 根已经大于最大的孩子 → 调整完成 if (root >= a[i]) break; // 孩子上移 a[k] = a[i]; k = i; // 继续向下调整 } a[k] = root;}7.4 建堆与排序
void HeapSort(int a[], int n) { int i, temp; // 1. 建堆：从最后一个非叶结点开始调整 // 最后一个非叶结点下标 = n/2 - 1 for (i = n / 2 - 1; i >= 0; i--) HeapAdjust(a, i, n);
// 2. 排序：反复取出堆顶（与最后一个交换），调整堆 for (i = n - 1; i > 0; i--) { temp = a[0]; // 堆顶（最大值）与最后元素交换 a[0] = a[i]; a[i] = temp; HeapAdjust(a, 0, i); // 调整剩余元素为新堆 }}7.5 堆排序过程示意
初始序列：[49, 38, 65, 97, 76, 13, 27, 49]
建堆后： [97, 76, 65, 49, 38, 13, 27, 49] ↑ ↑ 堆顶 末尾
第1趟：交换堆顶 97 和末尾 49，调整 → [76, 49, 65, 49, 38, 13, 27 | 97]
第2趟：交换堆顶 76 和末尾 27，调整 → [65, 49, 27, 49, 38, 13 | 76, 97]
...最终：[13, 27, 38, 49, 49, 65, 76, 97]7.6 性能分析
| 指标 | 值 |
|---|---|
| 建堆时间复杂度 | $O(n)$ |
| 每次调整 | $O(\log n)$ |
| 总时间复杂度 | $O(n\log n)$ |
| 空间复杂度 | $O(1)$ |
| 稳定性 | 不稳定 |
7.7 堆的插入与删除
插入：新元素放末尾，然后向上调整（与父结点比较，上浮） 删除：用最后一个元素替换被删元素，然后向下调整（下沉）
8. 归并排序
8.1 基本思想
将两个或两个以上的有序表合并成一个新的有序表。
2 路归并：将序列两两归并，重复直到整个序列有序。
初始: 49 38 65 97 76 13 27 49
第1趟： [38 49] [65 97] [13 76] [27 49] → 每2个归并第2趟： [38 49 65 97] [13 27 49 76] → 每4个归并第3趟： [13 27 38 49 49 65 76 97] → 全部归并8.2 合并两个有序子表
// 合并 a[low..mid] 和 a[mid+1..high]void Merge(int a[], int low, int mid, int high) { int *temp = (int *)malloc((high - low + 1) * sizeof(int)); int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; // 左边剩余 while (j <= high) temp[k++] = a[j++]; // 右边剩余
for (i = low, k = 0; i <= high; i++, k++) a[i] = temp[k]; free(temp);}8.3 递归实现
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); // 合并两个有序子表 }}8.4 性能分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | $O(n\log n)$（与初始序列无关） |
| 归并趟数 | $\lceil \log_2 n \rceil$ |
| 空间复杂度 | $O(n)$（需要辅助数组） |
| 稳定性 | 稳定 ✓ |
9. 基数排序
9.1 基本思想
不基于比较，而是根据关键字各位的值进行分配和收集。
9.2 LSD（最低位优先）过程
序列：278 109 063 930 589 184 505 269 008 083
按个位分配： 桶0：930 桶3：063, 083 桶4：184 桶5：505 桶8：278, 008 桶9：109, 589, 269收集： 930 063 083 184 505 278 008 109 589 269
按十位分配： 桶0：505, 008, 109 桶3：930 桶6：063, 269 桶7：278 桶8：083, 184, 589收集： 505 008 109 930 063 269 278 083 184 589
按百位分配： 桶0：008, 063, 083 桶1：109, 184 桶2：269, 278 桶5：505, 589 桶9：930收集： 008 063 083 109 184 269 278 505 589 9309.2 性能分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | $O(d(n + r))$ |
| 空间复杂度 | $O(r)$ |
| 稳定性 | 稳定 ✓ |
- $d$：关键字位数
- $n$：元素个数
- $r$：基数（桶的数量）
10. 各种排序对比总结 ★★★
| 排序方法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.3})$ | — | $O(n^2)$ | $O(1)$ | 不稳定 |
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 快速排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | 不稳定 |
| 简单选择 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $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)$ | 稳定 |
10.1 选排序方法的依据 ★
| 场景 | 推荐排序 |
|---|---|
| $n$ 较小（≤ 50） | 直接插入、简单选择 |
| $n$ 很大 | $O(n\log n)$ 算法 |
| 基本有序 | 直接插入、冒泡 |
| 要求稳定 | 归并、插入、冒泡、基数 |
| 要求空间少 | 堆排序 |
| 关键字结构复杂 | 简单选择（比较次数最少） |
10.2 记忆技巧
插入冒泡归并基 —— 稳定希尔快选堆 —— 不稳定
n² 三兄弟：插入、冒泡、选择nlogn 三兄弟：快速、堆、归并
"快选堆" = 不稳定 = 内部排序中效率最高的三个11. 考试重点题型
题型一：手工模拟排序过程 ★★★
给定序列
{49, 38, 65, 97, 76, 13, 27, 49}，写出：
- 快速排序各趟结果
- 堆排序（建堆 + 每趟结果）
- 希尔排序各趟结果
- 归并排序各趟结果
题型二：判断排序稳定性
判断序列中有相同关键字时，某排序算法是否改变其相对位置。
题型三：时间复杂度分析
给定初始序列状态（正序/逆序/随机），分析各排序算法的比较和移动次数。
题型四：堆的调整
给定一个完全二叉树序列，从最后一个非叶结点开始建堆，写出每一步。
题型五：基数和归并的特殊问题
- 基数排序为什么不需要比较？
- 归并排序需要用多大的辅助空间？
💡 希尔排序的最终定论：它是插入排序的改进，通过增量分组让数据逐步有序，从而发挥插入排序”基本有序时效率高”的优势。不是选择排序的优化！
