数据结构考研数据结构排序插入排序希尔排序冒泡排序快速排序简单选择排序堆排序归并排序基数排序计数排序外部排序败者树最佳归并树

【王道考研·数据结构】第八章排序（整章完整版）

Austoin2026-04-212026-04-21

引言

第八章“排序”是数据结构里最像“综合题”的一章。

前面学线性表、树、图时，重点是结构本身；到了排序，重点变成：

面对不同数据特点，应该选哪一种算法，用什么代价把无序变成有序。

这一章可以整理成六条主线：

排序的基本概念：稳定性、内部排序、外部排序、评价指标
插入类排序：直接插入、折半插入、希尔排序
交换类排序：冒泡排序、快速排序
选择类排序：简单选择、堆排序、堆的插入与删除
归并与非比较排序：归并、基数、计数
外部排序：多路平衡归并、败者树、置换-选择排序、最佳归并树

本篇把 E:\PPT 下第八章全部课件合并整理，并把 PDF 中动画很多、文字缺失较多的部分全部补全，尤其补上：

完整代码
复杂度与稳定性对比
易错点与易混淆点
课件里一带而过但考试常考的结论

图像化理解（Mermaid）

  mindmap
  root((第八章 排序))
    排序基本概念
      稳定性
      内部排序 / 外部排序
      时间 / 空间 / 适用场景
    内部排序
      插入排序
        直接插入
        折半插入
        希尔排序
      交换排序
        冒泡排序
        快速排序
      选择排序
        简单选择
        堆排序
      归并 / 非比较排序
        归并排序
        基数排序
        计数排序
    外部排序
      多路归并
      败者树
      置换-选择排序
      最佳归并树

一句话：排序题本质上是在比较“比较次数、移动次数、辅助空间、稳定性、I/O 成本”这五种代价。

一、排序的基本概念

1. 排序的定义

设有一组记录：

1	R1, R2, ..., Rn

每个记录都有关键字：

1	k1, k2, ..., kn

排序的目标是把这些记录按关键字递增或递减重新排列，使之满足：

1	k1 <= k2 <= ... <= kn

如果是降序，则改成：

1	k1 >= k2 >= ... >= kn

2. 关键字、记录、排序码

记录：待排序的数据元素
关键字：用来比较大小的数据项
主关键字：决定主要排序次序的关键字
次关键字：主关键字相同时进一步比较的关键字

例如学生记录按“总分”排序：

记录：某个学生的完整信息
关键字：总分

3. 稳定性

若序列中存在两个记录 Ri、Rj，它们的关键字相等：

1	keyi = keyj

若排序前 Ri 在 Rj 前面，排序后仍然在 Rj 前面，则称该排序算法稳定。

稳定性的意义

稳定性在“多关键字排序”中特别重要。

例如先按“班级”排序，再按“成绩”稳定排序，那么成绩相同的人，班级次序仍能保持。

一个典型例子

原序列：

1	(3,a) (1,b) (3,c) (2,d)

按第一个数字升序排序后：

若结果是：(1,b) (2,d) (3,a) (3,c)，则稳定
若结果是：(1,b) (2,d) (3,c) (3,a)，则不稳定

4. 内部排序与外部排序

内部排序

待排序记录能够全部装入内存，在内存中完成排序。

常见内部排序：

插入排序
冒泡排序
快速排序
堆排序
归并排序
希尔排序
计数排序
基数排序

外部排序

待排序记录太多，不能全部装入内存，排序时需要在内存和外存之间多次交换数据。

外部排序关心的核心不再只是比较次数，而是：

I/O 次数是否尽量少。

5. 评价排序算法的指标

（1）时间复杂度

通常看：

比较次数
元素移动次数
总运行时间数量级

（2）空间复杂度

是否需要额外辅助空间。

（3）稳定性

相同关键字记录相对次序是否保持不变。

（4）适应性

序列越接近有序，算法是否越快。

例如：

直接插入排序对“基本有序”序列很友好
快速排序若输入本来有序且枢轴选得差，反而可能退化

6. 比较排序的下界

基于比较的排序，平均情况下不可能突破：

1	O(n log2 n)

所以：

快速排序平均 O(n log n) 已经很优秀
堆排序 O(n log n)
归并排序 O(n log n)

而计数排序、基数排序之所以能到线性级，是因为它们不是纯比较排序。

二、排序算法总表（先建立全局认识）

算法	最好时间	平均时间	最坏时间	空间复杂度	稳定性	备注
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定	基本有序时很好
折半插入排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定	减少比较，不减少移动
希尔排序	与增量有关	常优于 O(n^2)	O(n^2)	O(1)	不稳定	插入排序升级版
冒泡排序	O(n)	O(n^2)	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(n+r)	稳定	非比较排序
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定	值域小时很好

稳定性总记忆

稳定

直接插入排序
折半插入排序
冒泡排序
归并排序
基数排序
计数排序

不稳定

希尔排序
简单选择排序
快速排序
堆排序

三、直接插入排序

1. 基本思想

把序列看成两部分：

前半部分：已经有序
后半部分：尚未排序

每一趟从后半部分取出一个元素，插入到前半部分合适的位置。

2. 排序过程示例

原序列：

1	49 38 65 97 76 13 27 49

过程：

第一趟：38 插到 49 前面
38 49 65 97 76 13 27 49

第二趟：65 已经在合适位置
38 49 65 97 76 13 27 49

第三趟：97 已经在合适位置
38 49 65 97 76 13 27 49

第四趟：76 插入到 65 和 97 之间
38 49 65 76 97 13 27 49

第五趟：13 插到最前面
13 38 49 65 76 97 27 49

第六趟：27 插到 13 和 38 之间
13 27 38 49 65 76 97 49

第七趟：49 插到两个 49 的后面、65 的前面
13 27 38 49 49 65 76 97

3. 完整代码

void InsertSort(int A[], int n) {
    for (int i = 1; i < n; ++i) {
        int temp = A[i];
        int j = i - 1;

        while (j >= 0 && A[j] > temp) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = temp;
    }
}

4. 复杂度分析

最好情况

原序列已经有序：

1	1 2 3 4 5 6

每趟只比较一次，不需要移动。

时间复杂度：O(n)

最坏情况

原序列完全逆序：

1	6 5 4 3 2 1

每次都要把元素插到最前面。

时间复杂度：O(n^2)

平均情况

时间复杂度：O(n^2)

空间复杂度

O(1)

5. 稳定性分析

直接插入排序是稳定的。

原因：

1	while (j >= 0 && A[j] > temp)

这里只移动严格大于 temp 的元素。

如果 A[j] == temp，不会继续前移，所以后来的相等元素会插在前面相等元素的后面。

6. 适用场景

数据量较小
序列基本有序
希望稳定排序
链式存储也适合

7. 易错点

忘记先保存 A[i]，导致数据被覆盖。
j 可能减到 -1，最后插入位置应是 j + 1。
条件若写成 A[j] >= temp，会破坏稳定性。

8. 易混淆点

直接插入排序稳定，但简单选择排序不稳定。
直接插入排序最好能到 O(n)，简单选择排序不行。

四、折半插入排序

1. 基本思想

直接插入排序的问题在于：

找插入位置时要线性查找

如果前半段已经有序，那就可以用折半查找定位插入位置。

2. 核心结论

折半插入排序：

减少了比较次数
没有减少移动次数

因此其总时间复杂度仍然通常记作：

O(n^2)

3. 完整代码

void BinaryInsertSort(int A[], int n) {
    for (int i = 1; i < n; ++i) {
        int temp = A[i];
        int low = 0;
        int high = i - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (A[mid] <= temp) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        for (int j = i - 1; j >= low; --j) {
            A[j + 1] = A[j];
        }
        A[low] = temp;
    }
}

4. 为什么仍是 O(n^2)

对于第 i 趟：

折半查找插入位置：O(log i)
元素后移：最坏 O(i)

总体：

1	Σ(O(log i) + O(i)) = O(n^2)

5. 稳定性分析

折半插入排序也可以做成稳定。

关键点在于：

当 A[mid] == temp 时，要把 low 往右移：

1
2
3

if (A[mid] <= temp) {
    low = mid + 1;
}

这样相等元素会插到原有相等元素后面。

6. 适用场景

顺序表
比较代价高于移动代价时稍有优势

7. 易错点

误以为折半插入排序整体变成 O(n log n)。
A[mid] == temp 时分支写错，容易破坏稳定性。
low 是最终插入位置，不是 mid。

五、希尔排序

1. 基本思想

希尔排序是“分组的插入排序”，也叫缩小增量排序。

它的核心思想是：

先让元素大跨度移动，尽早接近最终位置；最后再用增量为 1 的插入排序收尾。

2. 分组方式

设增量为 dk，则把序列中下标相差 dk 的元素分到一组。

例如序列：

1	49 38 65 97 76 13 27 49

若 dk = 4，则分组为：

(49, 76)
(38, 13)
(65, 27)
(97, 49)

然后每组分别做插入排序。

3. 完整代码

void ShellSort(int A[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = A[i];
            int j = i - gap;

            while (j >= 0 && A[j] > temp) {
                A[j + gap] = A[j];
                j -= gap;
            }
            A[j + gap] = temp;
        }
    }
}

4. 复杂度分析

希尔排序复杂度与增量序列密切相关。

教材中通常写：

最坏：O(n^2)
平均：通常优于直接插入排序

严格来说，不同增量序列可能得到不同性能，因此考试一般按教材结论写即可，不要自己乱写成唯一精确公式。

5. 稳定性分析

希尔排序是不稳定的。

原因：

元素按 gap 跨组移动
相等关键字元素可能跨过彼此
相对次序会被改变

6. 适用场景

中等规模数据
希望原地排序
追求比简单 O(n^2) 排序更好的平均性能

7. 易错点

误把“分组”理解为真的开多个数组。
认为每一趟后整个序列已经有序。
忽略增量序列会影响性能。
误认为希尔排序稳定。

8. 易混淆点

希尔排序本质上还是插入排序的改进。
它不是 O(n log n) 保证算法。
它和堆排序、快速排序都不稳定，但原因不同。

六、冒泡排序

1. 基本思想

从前往后两两比较相邻元素，若逆序则交换。

每一趟都会把一个较大元素“冒泡”到末尾。

2. 过程示例

原序列：

1	49 38 65 97 76 13 27 49

第一趟后，最大元素 97 到末尾。

第二趟后，次大元素到倒数第二位。

依此类推。

3. 完整代码

void BubbleSort(int A[], int n) {
    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]) {
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

4. 复杂度分析

最好情况

序列本来有序，并且带 swapped 标记：

时间复杂度：O(n)

平均 / 最坏情况

O(n^2)

空间复杂度

O(1)

5. 稳定性分析

冒泡排序是稳定的。

因为只在：

1	A[j] > A[j + 1]

时交换。

若相等则不交换，相对次序保持不变。

6. 适用场景

数据量小
需要稳定排序
教学演示“逆序对逐步消除”

7. 易错点

内层循环上界写错，应到 n - 1 - i。
忘记提前结束标志。
误以为冒泡比直接插入更适合“基本有序”。

8. 冒泡与插入的区别

冒泡：通过交换相邻逆序对实现有序
插入：通过后移元素 + 插入实现有序

在近乎有序的情况下，直接插入排序通常更实用。

七、快速排序

1. 基本思想

快速排序属于分治法。

步骤：

选一个枢轴 pivot
一趟划分，把比它小的放左边，比它大的放右边
对左右子区间递归做同样的事

2. 最核心：划分 Partition

快速排序真正的关键不在递归，而在：

如何高效且正确地完成一趟划分。

3. 常用实现：双指针挖坑法

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) {
        return;
    }
    int pivotPos = Partition(A, low, high);
    QuickSort(A, low, pivotPos - 1);
    QuickSort(A, pivotPos + 1, high);
}

4. 过程理解

例如：

1	49 38 65 97 76 13 27 49

若取第一个元素 49 为枢轴，一趟划分后会得到：

1	[比49小的部分] 49 [比49大的部分]

注意：

左右两边内部此时未必有序
只是枢轴已经到最终位置

5. 手算一趟划分（高频）

以序列：

1	49 38 65 97 76 13 27 49

为例，取首元素 49 为枢轴。

初始：
pivot = 49
[49, 38, 65, 97, 76, 13, 27, 49]
 low                             high

第一步：从右往左找第一个 `< 49` 的数

1	右侧依次看：49(>=49) 跳过，27(<49) 停下

把它放到左侧坑位：

1	[27, 38, 65, 97, 76, 13, 27, 49]

第二步：从左往右找第一个 `> 49` 的数

1
2
3

27(<=49) 跳过
38(<=49) 跳过
65(>49) 停下

把它放到右侧坑位：

1	[27, 38, 65, 97, 76, 13, 65, 49]

第三步：继续从右往左找 `< 49`

1
2
3

49(>=49) 跳过
65(>=49) 跳过
13(<49) 停下

填左坑：

1	[27, 38, 13, 97, 76, 13, 65, 49]

第四步：继续从左往右找 `> 49`

1 2	13(<=49) 跳过 97(>49) 停下

填右坑：

1	[27, 38, 13, 97, 76, 97, 65, 49]

第五步：继续从右往左找 `< 49`

1
2
3

97(>=49) 跳过
76(>=49) 跳过
此时 low == high，停止

最后把 pivot 填回：

1	[27, 38, 13, 49, 76, 97, 65, 49]

此时枢轴 49 已归位。

手算时你必须记住

一趟划分后，只保证枢轴位置正确。
左右两边只是“分别不大于 / 不小于枢轴”，内部不一定有序。
如果题目问“第 1 趟快排结果”，通常就是问“一次 Partition 之后”的结果，不是最终排序结果。

6. 复杂度分析

最好情况

每次都平均分成两半：

1	T(n) = 2T(n/2) + O(n)

得到：

1	O(n log n)

平均情况

O(n log n)

最坏情况

每次都极不平衡，例如：

原序列已有序
每次都取第一个元素做枢轴

则递归会退化成：

1	T(n) = T(n-1) + O(n)

得到：

O(n^2)

空间复杂度

平均：O(log n)（递归栈）
最坏：O(n)

7. 稳定性分析

快速排序是不稳定的。

因为划分过程中，元素会跨区间交换，相等元素相对次序可能改变。

8. 为什么快排平均性能强

虽然最坏会退化，但快排平均性能非常好，原因是：

常数因子小
原地划分，额外空间少
局部性好，缓存友好

9. 枢轴选择的影响

若每次取第一个元素作为枢轴：

在随机数据中通常没问题
在接近有序数据上很危险

工程上常见优化：

随机选枢轴
三数取中

10. 易错点

Partition 内部循环条件写错，容易死循环。
递归边界应是 if (low >= high) return;
左右递归区间写错，导致重复排枢轴。
误认为快排稳定。
误认为快排最坏也是 O(n log n)。

11. 易混淆点

快排平均快，但最坏没有堆排序稳。
快排原地，但归并稳定。
快排的不稳定来自交换，归并的稳定来自按序复制。

八、简单选择排序

1. 基本思想

每一趟从未排序区中选择最小元素，放到当前应放的位置。

2. 完整代码

void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (A[j] < A[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = A[i];
            A[i] = A[minIndex];
            A[minIndex] = temp;
        }
    }
}

3. 复杂度分析

无论原序列如何：

比较次数都差不多固定
都是 O(n^2)

所以：

最好：O(n^2)
平均：O(n^2)
最坏：O(n^2)

空间复杂度：

O(1)

4. 稳定性分析

简单选择排序是不稳定的。

原因：

每趟找到最小元素后直接和前面位置交换
这个交换可能把某个相等关键字元素跨过去

例如：

1	(2,a) (2,b) (1,c)

第一趟选择 (1,c) 与 (2,a) 交换，结果变成：

1	(1,c) (2,b) (2,a)

于是 (2,a) 和 (2,b) 相对次序改变。

5. 特点

比较次数较多
交换次数较少（最多 n-1 次）

6. 易错点

误认为“交换次数少”就一定更快。
误认为简单选择排序稳定。
忽视它最好情况也不能降到 O(n)。

九、堆的基本概念

1. 堆的定义

堆是一种满足以下条件的完全二叉树：

大根堆

任一非叶结点的值都：

>= 其左右孩子

小根堆

任一非叶结点的值都：

<= 其左右孩子

2. 顺序存储下的下标关系

若堆从下标 1 开始存：

父结点：i / 2
左孩子：2 * i
右孩子：2 * i + 1

3. 堆的核心操作

建堆
插入（上滤）
删除堆顶（下滤）

十、堆的插入与删除

1. 堆的插入（上滤）

思想

新元素先放到堆尾，再不断和父结点比较，必要时上移。

代码（大根堆）

void ShiftUp(int heap[], int index) {
    int temp = heap[index];
    while (index > 1 && heap[index / 2] < temp) {
        heap[index] = heap[index / 2];
        index /= 2;
    }
    heap[index] = temp;
}

void HeapInsert(int heap[], int& size, int value) {
    heap[++size] = value;
    ShiftUp(heap, size);
}

2. 删除堆顶（下滤）

思想

把堆尾元素放到堆顶，再沿着较大的孩子方向下滤。

代码（大根堆）

void ShiftDown(int heap[], int index, int size) {
    int temp = heap[index];
    for (int child = index * 2; child <= size; child *= 2) {
        if (child + 1 <= size && heap[child + 1] > heap[child]) {
            ++child;
        }
        if (heap[child] <= temp) {
            break;
        }
        heap[index] = heap[child];
        index = child;
    }
    heap[index] = temp;
}

int HeapDeleteTop(int heap[], int& size) {
    int top = heap[1];
    heap[1] = heap[size--];
    if (size > 0) {
        ShiftDown(heap, 1, size);
    }
    return top;
}

3. 时间复杂度

插入：O(log n)
删除堆顶：O(log n)

4. 易错点

插入是上滤，不是下滤。
删除堆顶后是局部调整，不是重新建堆。
大根堆和小根堆比较方向不要写反。

十一、堆排序

1. 基本思想

若要升序排序，可以使用大根堆：

先把整个数组建成大根堆
堆顶最大，和最后一个元素交换
堆长度减 1
对新的堆顶做下滤
重复直到只剩一个元素

2. 建堆为什么从最后一个非叶结点开始

完全二叉树中，最后一个非叶结点下标为：

n / 2

因为叶子天然满足堆性质，所以从 n/2 开始向前做下滤即可。

3. 完整代码

void HeapAdjust(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 >= 1; --i) {
        HeapAdjust(A, i, len);
    }
}

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; --i) {
        int temp = A[1];
        A[1] = A[i];
        A[i] = temp;
        HeapAdjust(A, 1, i - 1);
    }
}

上面代码默认数组从 1 开始存放。

4. 建堆手算（高频）

假设数组从 1 开始，原序列为：

1 2	下标： 1 2 3 4 5 数值： 5 17 10 84 19

要求建成大根堆。

最后一个非叶结点下标：

5 / 2 = 2

所以从 2 开始向前调整。

调整结点 2

当前：5 17 10 84 19
结点2 = 17，孩子为 84 和 19
较大孩子是 84
17 < 84，交换/下滤

得到：

1	5 84 10 17 19

调整结点 1

当前：5 84 10 17 19
结点1 = 5，孩子为 84 和 10
较大孩子是 84
5 < 84，下滤到位置2

继续看位置 2 的孩子：

1
2
3

孩子为 17 和 19
较大孩子是 19
5 < 19，继续下滤

最终：

1	84 19 10 17 5

这就是建堆结果。

建堆手算模板

1
2
3

从最后一个非叶结点 n/2 开始
对每个结点做“和较大孩子比，必要时下滤”
一直处理到根

5. 复杂度分析

建堆

O(n)

这是一个高频考点，不能写错成 O(n log n)。

排序阶段

共做 n-1 次“交换 + 下滤”
每次下滤 O(log n)

所以总复杂度：

1	O(n log n)

空间复杂度

O(1)

6. 稳定性分析

堆排序是不稳定的。

原因：

堆顶与堆尾交换
相等元素可能跨越很长距离
相对次序被改变

7. 堆排序前两趟手算

仍以建好的大根堆：

1	84 19 10 17 5

为例。

第一趟

交换堆顶和堆尾：

1	5 19 10 17 84

其中 84 已就位，不再参与堆调整。

对前 4 个元素做下滤：

1
2
3

5 与孩子 19、10 比，选 19
19 上移，5 下滤
再和 17 比，17 上移

得到：

1	19 17 10 5 84

第二趟

交换堆顶和当前堆尾：

1	5 17 10 19 84

其中 19、84 已归位。

对前 3 个元素继续下滤：

1	17 5 10 19 84

继续做下去，最终升序：

1	5 10 17 19 84

堆排序手算时必须记住

大根堆用于升序，小根堆用于降序。
每一趟是“堆顶和堆尾交换 + 缩堆 + 下滤”。
已换到末尾的元素视为已经排好序。

8. 特点

最坏时间也稳定在 O(n log n)
原地排序
但不稳定

9. 易错点

建堆复杂度写错。
搞反“大根堆得到升序、小根堆得到降序”。
把堆排序误写成稳定排序。

10. 与快速排序对比

堆排序：最坏也 O(n log n)，更稳
快速排序：平均更快，但最坏可能 O(n^2)

十二、归并排序

1. 基本思想

归并排序采用分治法：

把序列一分为二
分别排序
把两个有序子序列归并成一个新的有序序列

2. 归并操作 Merge

归并排序真正的关键是：

如何把两个有序表合并成一个有序表。

3. 完整代码

void Merge(int A[], int temp[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right) {
        if (A[i] <= A[j]) {
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = A[i++];
    }
    while (j <= right) {
        temp[k++] = A[j++];
    }

    for (int p = left; p <= right; ++p) {
        A[p] = temp[p];
    }
}

void MergeSortRec(int A[], int temp[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    MergeSortRec(A, temp, left, mid);
    MergeSortRec(A, temp, mid + 1, right);
    Merge(A, temp, left, mid, right);
}

void MergeSort(int A[], int n) {
    int* temp = new int[n];
    MergeSortRec(A, temp, 0, n - 1);
    delete[] temp;
}

4. 非递归写法思想

也可以按子表长度：

1	1 -> 2 -> 4 -> 8 -> ...

逐步做两两归并。

5. 两路归并手算（高频）

设两个有序子表：

1 2	L = [13, 49, 76] R = [27, 38, 97]

归并过程：

比较 13 和 27 -> 取 13
结果：[13]

比较 49 和 27 -> 取 27
结果：[13, 27]

比较 49 和 38 -> 取 38
结果：[13, 27, 38]

比较 49 和 97 -> 取 49
结果：[13, 27, 38, 49]

比较 76 和 97 -> 取 76
结果：[13, 27, 38, 49, 76]

左表空，右表剩余 97 直接接到末尾
结果：[13, 27, 38, 49, 76, 97]

手算模板

1
2
3

两个指针分别指向两段首元素
每次取较小者放入结果表
某一段先空后，另一段整体接到末尾

6. 复杂度分析

递推式：

1	T(n) = 2T(n/2) + O(n)

得到：

最好：O(n log n)
平均：O(n log n)
最坏：O(n log n)

空间复杂度：

O(n)

7. 稳定性分析

归并排序是稳定的。

关键点在合并时：

1	if (A[i] <= A[j])

当相等时，优先取左边那个元素，因此相对次序保持不变。

8. 适用场景

需要稳定排序
数据量较大
链表排序很适合归并
外部排序的归并阶段本质也是归并思想

9. 易错点

辅助数组拷回原数组时区间边界写错。
误认为归并排序是原地排序。
递归边界漏掉 left >= right。

十三、基数排序

1. 基本思想

基数排序不直接比较关键字整体大小，而是按“位”来排。

最常见的是LSD（最低位优先）：

先按个位分配、收集
再按十位分配、收集
再按百位……

直到最高位

2. 为什么它能正确

因为每一趟排序必须是稳定的。

也就是说：

后一趟按更高位分类时
之前低位排好的顺序不能被破坏

3. 适用条件

基数排序适合：

关键字可以拆成多个位
位数 d 不大
每位取值范围 r 不大

例如：

多位整数
身份证号
日期
固定长度字符串

4. 复杂度

若：

n：记录数
d：位数
r：每位取值范围（基数）

则时间复杂度：

1	O(d(n + r))

空间复杂度：

O(n + r)

5. 稳定性

基数排序是稳定的。

前提是每一趟分配与收集都稳定。

6. 一个简单实现（十进制 LSD）

#include <vector>
using namespace std;

void RadixSort(vector<int>& a) {
    if (a.empty()) {
        return;
    }

    int maxValue = a[0];
    for (int x : a) {
        if (x > maxValue) {
            maxValue = x;
        }
    }

    vector<int> output(a.size());

    for (int exp = 1; maxValue / exp > 0; exp *= 10) {
        int count[10] = {0};

        for (int x : a) {
            int digit = (x / exp) % 10;
            ++count[digit];
        }

        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        for (int i = (int)a.size() - 1; i >= 0; --i) {
            int digit = (a[i] / exp) % 10;
            output[count[digit] - 1] = a[i];
            --count[digit];
        }

        for (int i = 0; i < (int)a.size(); ++i) {
            a[i] = output[i];
        }
    }
}

上面代码默认处理非负整数。

7. 易错点

误以为基数排序只能排十进制数。
忽视“每一趟必须稳定”。
把基数排序和计数排序混成一个东西。

8. 易混淆点

计数排序：按“值”统计
基数排序：按“位”统计，通常每位内部会借助计数排序思想

十四、计数排序

1. 基本思想

如果关键字是整数，且值域不大，就可以统计每个值出现了多少次，再恢复成有序序列。

2. 计数排序的关键步骤

找到最小值 minValue 和最大值 maxValue
开辟计数数组 count
统计每个值出现次数
求前缀和，得到每个值的最终位置区间
从后向前扫描原数组，把元素稳定放入结果数组

3. 为什么要从后向前回填

为了保证稳定性。

如果从前往后填，具有相同关键字的元素可能先后颠倒。

4. 手算一遍前缀和定位

原数组：

1	[2, 5, 3, 0, 2, 3, 0, 3]

值域：

0 ~ 5

第一步：统计频次

1 2	值： 0 1 2 3 4 5 count： 2 0 2 3 0 1

第二步：做前缀和

1 2	值： 0 1 2 3 4 5 count： 2 2 4 7 7 8

这表示：

0 最后一个应放在下标 1
2 最后一个应放在下标 3
3 最后一个应放在下标 6
5 最后一个应放在下标 7

第三步：从后往前回填

从原数组最后一个 3 开始：

3 -> 放到 output[6]
count[3] 变成 6

0 -> 放到 output[1]
count[0] 变成 1

3 -> 放到 output[5]
count[3] 变成 5

2 -> 放到 output[3]
count[2] 变成 3

0 -> 放到 output[0]
count[0] 变成 0

3 -> 放到 output[4]
count[3] 变成 4

5 -> 放到 output[7]
count[5] 变成 7

2 -> 放到 output[2]
count[2] 变成 2

最终结果：

1	[0, 0, 2, 2, 3, 3, 3, 5]

这个过程为什么稳定

因为相同元素从后往前放，后出现的元素先占“最后位置”，前出现的元素会自然排在它前面。

5. 完整代码（支持负数、稳定版）

#include <vector>
using namespace std;

void CountingSort(vector<int>& a) {
    if (a.size() <= 1) {
        return;
    }

    int minValue = a[0];
    int maxValue = a[0];
    for (int x : a) {
        if (x < minValue) {
            minValue = x;
        }
        if (x > maxValue) {
            maxValue = x;
        }
    }

    int range = maxValue - minValue + 1;
    vector<int> count(range, 0);
    vector<int> output(a.size());

    for (int x : a) {
        ++count[x - minValue];
    }

    for (int i = 1; i < range; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = (int)a.size() - 1; i >= 0; --i) {
        int index = a[i] - minValue;
        output[count[index] - 1] = a[i];
        --count[index];
    }

    for (int i = 0; i < (int)a.size(); ++i) {
        a[i] = output[i];
    }
}

6. 复杂度分析

设值域长度为 k：

时间复杂度：O(n + k)
空间复杂度：O(n + k)

7. 稳定性分析

计数排序可以是稳定的。

前提：

使用前缀和
从后往前填结果数组

8. 适用场景

数据是整数
值域不大
需要稳定排序

9. 不适用场景

值域非常大
数据不是容易离散化的整数

例如：

1 2	n = 1000 但数值范围是 -10^9 到 10^9

那计数数组会过大，不划算。

10. 易错点

忘记处理负数偏移。
从前往后回填，导致稳定性被破坏。
误认为计数排序是原地排序。
误认为计数排序适合所有整数排序。

11. 易混淆点

计数排序是非比较排序
它突破比较排序下界，不代表“永远最快”
前提条件很强：值域必须相对小

十五、比较排序与非比较排序总结

1. 比较排序

通过关键字两两比较决定次序：

插入排序
希尔排序
冒泡排序
快速排序
简单选择排序
堆排序
归并排序

平均下界：

1	O(n log n)

2. 非比较排序

不依赖“谁和谁比较”，而是利用值域或位信息：

基数排序
计数排序

3. 高频考点

比较排序下界不适用于计数排序和基数排序。

这是选择题、判断题高频点。

十六、外部排序的基本思想

1. 为什么需要外部排序

如果数据量太大，内存无法一次装下全部待排记录，就不能像内部排序那样直接处理整个数组。

这时必须：

把数据分批装入内存
先形成若干初始有序段
再多路归并

2. 外部排序两大阶段

第一阶段：生成初始归并段

把文件分批读入内存，在内存中排序后输出成多个有序小文件。

第二阶段：多路归并

把多个有序段归并成更大的有序段，直到只剩一个最终有序文件。

3. 外部排序最关心什么

内部排序最关心比较次数；

外部排序最关心：

磁盘 I/O 次数。

4. 图像化理解

大文件
  |
  +-- 分块读入内存
  +-- 每块内部排好序
  +-- 输出初始归并段
  +-- 多路归并
  +-- 最终有序文件

十七、多路平衡归并

1. 基本思想

若有 k 个有序归并段，可以一次同时归并这 k 路。

这就叫：

k 路归并

2. 路数增大有什么好处

路数越大：

每一趟能合并更多段
归并趟数会减少

3. 但为什么不能无限增大

因为：

每一路都需要输入缓冲区
还需要输出缓冲区
每次从 k 路中选最小值也会更复杂

所以路数不是越大越好，而是要平衡：

缓冲区个数
每次选最小的成本
总归并趟数

4. 朴素 k 路归并伪代码

1
2
3

重复直到所有归并段耗尽：
  从 k 个当前记录中选最小者输出
  该记录所在归并段读入下一个记录

5. 易错点

误以为多路越大越好。
忽略输入缓冲区和输出缓冲区需求。
只讨论比较次数，不讨论 I/O。

十八、败者树

1. 败者树的作用

在 k 路归并中，若每次都直接比较 k 个当前元素，代价较高。

败者树就是为了解决：

如何更快地反复从 k 路中选出当前最小记录。

2. 基本思想

把每一路当前记录看成“参赛选手”，构成一棵完全二叉树。

比较时：

胜者继续向上
败者留在内部结点

最终：

根外保存总胜者
树中保存一路比较过程的“败者”

3. 为什么叫败者树

因为内部结点存的是败者，不是胜者。

4. 更新的优势

当某一路输出一个记录后，只需要让这一路新记录沿原路径重新比赛。

于是每次调整成本：

O(log k)

5. 复杂度

建树：O(k)
每次输出后调整：O(log k)

6. 与朴素比较的区别

朴素选最小：每次 O(k)
败者树：每次 O(log k)

7. 易错点

内部结点存的是败者，不是胜者。
它优化的是“选最小”内部代价，不直接减少 I/O 次数。
不要和堆混成同一结构，它们目标不同。

十九、置换-选择排序

1. 它解决什么问题

如果工作区一次只能容纳 m 个记录，那么普通方法通常只能产生长度约为 m 的初始归并段。

置换-选择排序希望做到：

生成比工作区更长的初始归并段。

2. 核心思想

从工作区中不断选最小记录输出。

读入新记录替补时：

如果它不小于当前归并段最后输出值，可以继续属于当前归并段
如果它更小，就不能放进当前归并段，只能“冻结”到下一段

3. 关键字 MINIMAX

可以把当前归并段已输出的最后一个值看作当前段的下界。

新读入记录若小于这个下界，就不属于本段。

4. 重要结论

在随机输入下，长度为 m 的工作区，用置换-选择排序生成的初始归并段平均长度约为：

2m

这是很高频的结论。

5. 为什么它重要

初始归并段越长：

归并段个数越少
后续归并趟数越少
外部排序总 I/O 更少

6. 易错点

冻结元素不是丢弃，而是留给下一归并段。
平均长度约 2m 是随机输入下的结论，不是绝对值。
不要把它误当成内部排序算法，它服务于外部排序的“初始段生成”。

二十、最佳归并树

1. 问题背景

如果各初始归并段长度不同，那么归并顺序会影响总读写代价。

因此问题变成：

怎样安排归并顺序，才能让总 I/O 最小。

2. 核心思想

最佳归并树本质上和 Huffman 树思想一致：

让权值较小的归并段尽量处于更深层，使带权路径长度 WPL 最小。

3. 若是二路归并

就可以按二叉 Huffman 树构造。

4. 若是 k 路归并

就构造 k 叉 Huffman 树 思想对应的归并树。

5. 为什么有时要补 0

若有 r 个初始归并段，构造 k 叉归并树时要满足：

1	(r - 1) % (k - 1) == 0

若不满足，就要补若干个0 权值虚段。

补 0 的作用：

使树结构合法
不增加 WPL

6. 代价公式

若每条记录一次归并需要一次读和一次写，则总 I/O 常写为：

2 * WPL

7. 手算例题：二路最佳归并树

有 4 个初始归并段，长度分别为：

1	2, 3, 7, 9

若做二路归并，求最优归并代价。

第一步：先合并最小的两个

2 + 3 = 5

当前集合：

5, 7, 9

第二步：继续合并最小的两个

1	5 + 7 = 12

当前集合：

9, 12

第三步：继续合并

1	9 + 12 = 21

总 WPL

1	5 + 12 + 21 = 38

若题目说一次归并要“读一次 + 写一次”，则总 I/O：

1	2 * 38 = 76

8. 手算例题：三路归并补 0

若有 5 个归并段，要构造 3 路最佳归并树。

先检查：

(r - 1) % (k - 1)
= (5 - 1) % (3 - 1)
= 4 % 2
= 0

这时不需要补 0。

如果是 6 个归并段：

1
2
3

(6 - 1) % (3 - 1)
= 5 % 2
= 1

则必须补一个 0 权值虚段，使总叶子数满足 3 叉结构条件。

9. 易错点

最佳归并树不一定是二叉，要看几路归并。
补 0 不是“补一条真的归并段”。
题目若给多路归并，必须检查是否满足 (r - 1) % (k - 1) == 0。

二十一、整章高频易混淆点

1. 直接插入排序 vs 折半插入排序

直接插入：顺序找位置
折半插入：二分找位置
但二者总体都常记作 O(n^2)

2. 直接插入排序 vs 希尔排序

直接插入：每次移动相邻元素
希尔排序：先跨 gap 大步移动
直接插入稳定，希尔不稳定

3. 冒泡排序 vs 简单选择排序

冒泡稳定、可提前结束
简单选择不稳定、最好情况也还是 O(n^2)

4. 快速排序 vs 堆排序

快排：平均更快，但最坏会退化
堆排：最坏也 O(n log n)，更稳
两者都不稳定

5. 快速排序 vs 归并排序

快排：原地、平均快、不稳定
归并：稳定、时间稳、需要额外空间

6. 计数排序 vs 基数排序

计数排序：直接按值统计，值域要小
基数排序：按位排，每一位通常借助计数思想

7. 内部排序 vs 外部排序

内排关心比较/移动次数
外排更关心 I/O 次数和归并趟数

8. 败者树 vs 堆

堆：常用于优先队列、堆排序
败者树：常用于 k 路归并快速选最小

二十二、考试高频结论清单

稳定排序：直接插入、折半插入、冒泡、归并、基数、计数。
不稳定排序：希尔、简单选择、快速、堆排序。
折半插入排序总体仍是 O(n^2)。
堆排序建堆复杂度是 O(n)，不是 O(n log n)。
快速排序平均 O(n log n)，最坏 O(n^2)。
归并排序无论最好平均最坏都是 O(n log n)。
比较排序平均下界是 O(n log n)。
计数排序和基数排序属于非比较排序。
外部排序的核心成本是 I/O，不是比较次数。
置换-选择排序生成的初始归并段平均长度约为 2m。
最佳归并树本质是 Huffman 树思想。
k 路最佳归并树若不满足结构条件，要补 0 权值虚段。

二十三、算法选型速记

1. 若数据基本有序

优先考虑：

直接插入排序

2. 若数据量大，追求平均性能

优先考虑：

快速排序

3. 若要求最坏时间也稳定在 `O(n log n)`

优先考虑：

堆排序
归并排序

4. 若要求稳定且 `O(n log n)`

优先考虑：

归并排序

5. 若值域小

优先考虑：

计数排序

6. 若关键字位数固定且可拆分

优先考虑：

基数排序

7. 若数据无法全部放入内存

优先考虑：

外部排序

二十四、本章做题模板

1. 一看到排序题，先判断四件事

是否要求稳定
是否要求原地
数据是否近乎有序
关键字是否有值域/位数特征

2. 一看到复杂度比较题，先背住三组核心算法

1
2
3

O(n^2)：插入 / 冒泡 / 选择 / 希尔最坏
O(n log n)：快排平均 / 堆排 / 归并
线性级：计数 / 基数（有条件）

3. 一看到外部排序题，先问三件事

1
2
3

初始归并段怎么生成
归并路数是多少
是否需要败者树 / 最佳归并树 / 补0

二十五、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

折半插入排序 vs 快速排序
- 两者都用到了“二分”味道的思想，但完全不是一回事。
- 折半插入是用折半找插入位置，仍需大量移动。
- 快速排序是分治划分，不做“插入”。
堆排序 vs 简单选择排序
- 都属于“选择”思想。
- 简单选择是每趟线性找最小。
- 堆排序是利用堆结构快速取最值。
基数排序 vs 计数排序
- 计数排序按“整体值”计数。
- 基数排序按“每一位”多趟处理。
归并排序 vs 外部排序
- 归并排序是内部排序算法。
- 外部排序的归并阶段会大量使用归并思想，但不是同一个概念层级。
败者树 vs 最佳归并树
- 败者树：解决“k 路归并时如何高效选最小”。
- 最佳归并树：解决“多段归并顺序怎样总代价最小”。

B. 易错点（为什么错 + 怎么改）

把折半插入排序写成 O(n log n)
- 错因：只看到折半查找，忽略了后移元素。
- 正解：比较次数下降，但移动次数仍可达平方级，所以总体仍记 O(n^2)。
把建堆复杂度写成 O(n log n)
- 错因：以为每个结点都要下滤 log n 层。
- 正解：底层结点多但调整短，整体加总是 O(n)。
认为快速排序稳定
- 错因：把“枢轴归位”误以为“相等元素不交换”。
- 正解：划分过程会发生跨区间交换，不稳定。
认为计数排序不稳定
- 错因：只会写简单计数恢复版。
- 正解：若使用前缀和并从后往前回填，计数排序是稳定的。
把外部排序重点写成比较次数
- 错因：把内部排序评价方式照搬外排。
- 正解：外部排序最重要的是 I/O 次数和归并趟数。
最佳归并树忘记补 0
- 错因：只记住 Huffman 树思想，没记住 k 叉结构条件。
- 正解：先检查 (r - 1) % (k - 1) 是否为 0，不满足就补 0 权值虚段。

C. 本章做题顺序建议

先判断：内部排序 / 外部排序
  |
  +-- 若是内部排序：先看是否要求稳定、是否原地、是否近乎有序
  |
  +-- 若是非比较排序：先看值域和位数条件
  |
  +-- 若是外部排序：先看归并段、路数、败者树、最佳归并树

二十六、书签级思维导图复现（第八章，Mermaid）

  mindmap
  root((第8章 排序))
    8.1 排序基础
      稳定性
      内部排序/外部排序
      时间/空间/适应性指标
    8.2 插入类
      直接插入
      折半插入
      希尔排序
    8.3 交换类
      冒泡排序
      快速排序（Partition）
    8.4 选择类
      简单选择
      堆排序（建堆+下滤）
    8.5 归并与非比较
      归并排序
      计数排序
      基数排序
    8.6 外部排序
      多路平衡归并
      败者树
      置换-选择排序
      最佳归并树（含补0条件）

二十七、PDF 例题与知识点补充（排序）

例题 1：稳定排序集合

题目：常见排序中，哪些属于稳定排序？

答案：直接插入、折半插入、冒泡、归并、计数、基数。

详细解析：

稳定性指相等关键字排序后相对次序不变。
这些算法在标准实现下可保持相等元素先后顺序。

例题 2：不稳定排序集合

题目：常见排序中，哪些通常是不稳定排序？

答案：希尔、简单选择、快速、堆排序。

详细解析：

这类算法会发生跨区交换或大跨度移动。
相等关键字的原始相对顺序可能被打乱。

例题 3：折半插入复杂度误区

题目：折半插入排序为什么时间复杂度仍是 O(n^2)？

答案：折半只降低比较次数，元素移动次数仍是平方级。

详细解析：

插入位置可二分定位到 O(log n)。
但插入时平均仍需移动约 O(n) 个元素。
累计 n 趟后，总体仍为 O(n^2)。

例题 4：快排一趟划分结果

题目：快速排序执行一趟 Partition 后，能保证什么性质？

答案：仅保证枢轴最终归位，左区都不大于枢轴、右区都不小于枢轴，子区内部未必有序。

详细解析：

Partition 只完成“按枢轴分治”的一次切分。
左右子区仍需递归排序才能整体有序。

例题 5：快排最坏场景

题目：快速排序在什么情况下会退化到最坏复杂度？

答案：每次划分都极不平衡（如 1:(n-1)）时退化到 O(n^2)。

详细解析：

若枢轴总选到最小或最大值，递归深度接近 n。
每层仍要线性扫描，累计形成平方级。

例题 6：建堆复杂度

题目：为什么堆排序中的“建堆”复杂度是 O(n) 而不是 O(n log n)？

答案：底层结点多且下滤高度小，整体摊还后为线性。

详细解析：

自底向上建堆时，越靠近叶子结点，下滤步数越少。
各层下滤代价求和后是线性级别。

例题 7：堆排序复杂度

题目：堆排序在时间和空间上的典型复杂度是什么？

答案：最好/平均/最坏均为 O(n log n)，额外空间 O(1)。

详细解析：

每轮取堆顶后要做一次 O(log n) 下滤。
共进行约 n 轮，时间 O(n log n)。
原地操作，辅助空间常数级。

例题 8：归并排序复杂度

题目：归并排序的时间与空间复杂度结论是什么？

答案：最好/平均/最坏都为 O(n log n)，辅助空间 O(n)。

详细解析：

递归层数约 log n。
每层归并总工作量约 n。
归并时需额外数组暂存结果。

例题 9：归并稳定性来源

题目：归并排序为什么可以稳定？

答案：归并阶段遇到相等关键字时优先取左段元素，可保持原相对顺序。

详细解析：

左段元素在原序列中必先于右段对应元素。
相等时先取左段即可保证稳定性传递到最终结果。

例题 10：计数排序适用条件

题目：计数排序适合哪些数据分布？

答案：关键字是整数且值域范围不大时最合适。

详细解析：

计数排序空间开销与值域大小 k 相关。
当 k 远大于 n 时，空间与初始化代价过高，不经济。

例题 11：计数排序稳定性条件

题目：如何实现稳定的计数排序？

答案：先做前缀和，再按原数组从后向前回填输出数组。

详细解析：

前缀和提供每个关键字的最终区间末位置。
从后向前放置可保持相等元素原有先后顺序。

例题 12：基数排序关键条件

题目：基数排序正确性的关键前提是什么？

答案：按位分配-收集多趟执行，且每一趟内部排序必须稳定。

详细解析：

低位结果要被高位排序“继承”。
若某一趟不稳定，低位已建立的次序会被破坏。

例题 13：外部排序核心指标

题目：评价外部排序效率时最关键看什么？

答案：主要看磁盘 I/O 次数与归并趟数。

详细解析：

外部排序瓶颈通常在磁盘读写，而不是 CPU 比较。
减少归并趟数本质上是在减少全量数据重读写次数。

例题 14：败者树作用

题目：k 路归并中引入败者树的主要作用是什么？

答案：加速“选当前最小归并段”过程，使每次更新为 O(log k)。

详细解析：

败者树维护多路比较结果，根位置能快速得到当前最小值。
输出一个元素后只需沿其路径重赛，不必全量重比。

例题 15：k 路最佳归并补 0

题目：构造 k 叉最佳归并树时，为什么有时要补 0 权值段？

答案：为满足满 k 叉树条件 (r-1)%(k-1)==0，不足时补 0 权值虚段。

详细解析：

最佳归并树的结构约束决定叶子数量必须满足该同余条件。
补 0 权值段不增加比较代价，但能让树形合法。
这样才可按哈夫曼式策略得到最优归并代价。

二十八、第八章必背核对表

稳定/不稳定排序名单必须准确。
折半插入总体复杂度仍是平方级。
快排最坏可退化，堆排最坏稳定在 O(n log n)。
建堆复杂度是 O(n)。
归并稳定但非原地。
计数/基数是非比较排序，受条件约束。
外部排序主成本是 I/O。
最佳归并树补 0 条件必须会检验。

总结

第八章“排序”真正的核心不是把十个算法孤立背下来，而是建立一个统一视角：

比较排序还是非比较排序
稳定还是不稳定
原地还是需要额外空间
平均快还是最坏稳
内存内处理还是外部 I/O 主导

从考研角度，必须真正吃透的点是：

直接插入、折半插入、希尔三者关系
冒泡、快速、选择、堆排序的差异
归并、计数、基数的适用条件
外部排序中多路归并、败者树、置换-选择、最佳归并树

如果把这些“为什么”真正弄明白，第八章就不只是会背复杂度表，而是能在题目里快速判断：

哪种排序适合当前数据，为什么它快，为什么它慢，为什么它稳定，为什么它不稳定。

作者：[Austoin]
参考资料：王道考研《数据结构》第八章全部课件（E:\PPT）

引言

图像化理解（Mermaid）

一、排序的基本概念

1. 排序的定义

2. 关键字、记录、排序码

3. 稳定性

稳定性的意义

一个典型例子

4. 内部排序与外部排序

内部排序

外部排序

5. 评价排序算法的指标

（1）时间复杂度

（2）空间复杂度

（3）稳定性

（4）适应性

6. 比较排序的下界

二、排序算法总表（先建立全局认识）

稳定性总记忆

稳定

不稳定

三、直接插入排序

1. 基本思想

2. 排序过程示例

3. 完整代码

4. 复杂度分析

最好情况

最坏情况

平均情况

空间复杂度

5. 稳定性分析

6. 适用场景

7. 易错点

8. 易混淆点

四、折半插入排序

1. 基本思想

2. 核心结论

3. 完整代码

4. 为什么仍是 O(n^2)

5. 稳定性分析

6. 适用场景

7. 易错点

五、希尔排序

1. 基本思想

2. 分组方式

3. 完整代码

4. 复杂度分析

5. 稳定性分析

6. 适用场景

7. 易错点

8. 易混淆点

六、冒泡排序

1. 基本思想

2. 过程示例

3. 完整代码

4. 复杂度分析

最好情况

平均 / 最坏情况

空间复杂度

5. 稳定性分析

6. 适用场景

7. 易错点

8. 冒泡与插入的区别

七、快速排序

1. 基本思想

2. 最核心：划分 Partition

3. 常用实现：双指针挖坑法

4. 过程理解

5. 手算一趟划分（高频）

第一步：从右往左找第一个 < 49 的数

第二步：从左往右找第一个 > 49 的数

第三步：继续从右往左找 < 49

第四步：继续从左往右找 > 49

第五步：继续从右往左找 < 49

手算时你必须记住

6. 复杂度分析

最好情况

平均情况

最坏情况

空间复杂度

第一步：从右往左找第一个 `< 49` 的数

第二步：从左往右找第一个 `> 49` 的数

第三步：继续从右往左找 `< 49`

第四步：继续从左往右找 `> 49`

第五步：继续从右往左找 `< 49`