考研笔记

各种内部排序算法的比较及应用

这一节是全章的总账，教材开篇就说：「对各种排序算法的比较是考研常考的内容。」

比较基于五个因素：时间复杂度、空间复杂度、稳定性、适用性和过程特征。前四个查表 8.1 就行，第五个「过程特征」查不到表，只能靠理解——而它恰恰是综合题的常客。

机制

表 8.1 各种排序算法的性质

算法种类最好平均最坏空间复杂度是否稳定
直接插入排序是
冒泡排序是
简单选择排序否
希尔排序———否
快速排序否
堆排序否
二路归并排序是
基数排序是

边界辨析：

希尔排序那一行的三个时间格子是空的，这是教材有意为之： 「因为希尔排序的时间复杂度依赖于增量函数，所以无法准确给出其时间复杂度。」 表格标题下还有一句：「其中空间复杂度仅列举了平均情况的复杂度」—— 所以快速排序那格写 ，最坏是 ，表里没写但要知道。

五个因素逐条

① 从时间复杂度看

  • 简单选择排序、直接插入排序和冒泡排序平均情况下时间复杂度都为 ，且实现过程也较为简单，但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 ，而简单选择排序则与序列的初始状态无关。
  • 希尔排序作为插入排序的拓展，对较大规模的数据都可以达到很高的效率，但目前未得出其精确的渐近时间。
  • 堆排序利用了一种称为堆的数据结构，可以在线性时间内完成建堆，且在 内完成排序过程。
  • 快速排序基于分治的思想，虽然最坏情况下的时间复杂度会达到 ，但平均性能可以达到 ，在实际应用中常常优于其他排序算法。
  • 归并排序同样基于分治的思想，但其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 。

② 从空间复杂度看

  • 简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需借助常数个辅助空间。
  • 快速排序需要借助一个递归工作栈，平均大小为 ，最坏情况下可能会增长到 。
  • 二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为 。虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

③ 从稳定性看

稳定不稳定
插入排序、冒泡排序、归并排序、基数排序简单选择排序、快速排序、希尔排序、堆排序
  • 平均时间复杂度为 的稳定排序算法只有归并排序。
  • 对于不稳定的排序算法，只需举出一个不稳定的实例即可。
  • 「对于排序算法的稳定性，读者应能从算法本身的原理上去理解，而不应拘泥于死记硬背。」

④ 从适用性看

仅适用于顺序存储顺序 + 链式都适用
折半插入排序、希尔排序、快速排序、堆排序直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序

关联对照：

「仅顺序」那一栏的四个算法有一个共同点：都需要按下标随机跳跃。 折半插入要折半定位、希尔要跳增量、快排要双指针对撞、堆排序要 / 定位孩子—— 链表做不到 随机存取，所以它们都用不了。 这与 7.2.2 折半查找只能顺序存储 是同一条理由，不必单独记。

⑤ 从过程特征看

采用不同的排序算法，在一趟或几趟处理后的排序结果通常是不同的，考研题中经常出现给出一个待排序的初始序列和已部分排序的序列，问其采用何种排序算法。这就要求对各类排序算法的过程特征十分熟悉。

算法每趟之后的特征
冒泡排序、简单选择排序、堆排序每趟处理后都能产生当前的最大值或最小值（即已在最终位置）
快速排序一趟处理至少能确定一个元素的最终位置（枢轴），位置不固定
直接插入排序前 个元素有序，但不一定在最终位置
希尔排序相隔固定增量的元素成组有序
归并排序每趟后长度为 的各段内部有序

选取排序算法需要考虑的因素

  1. 待排序的元素个数 。
  2. 待排序的元素的初始状态。
  3. 关键字的结构及其分布情况。
  4. 稳定性的要求。
  5. 存储结构及辅助空间的大小限制等。

排序算法小结

  1. 若 较小，可采用直接插入排序或简单选择排序。直接插入排序所需的记录移动次数较简单选择排序的多，因此当记录本身信息量较大时，用简单选择排序较好。
  2. 若 较大，应采用时间复杂度为 的排序算法：快速排序、堆排序或归并排序。
    • 当待排序的关键字随机分布时，快速排序被认为是目前基于比较的内部排序算法中最好的算法。
    • 堆排序所需的辅助空间少于快速排序，且不会出现快速排序可能的最坏情况，这两种排序都是不稳定的。
    • 若要求稳定且时间复杂度为 ，可选用归并排序。
  3. 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
  4. 在基于比较的排序算法中，每次比较两个关键字的大小之后，仅出现两种可能的转移——由此可用决策树论证：基于比较的排序算法在最坏情况下至少需要 次比较，即 是比较类排序的下界。这也是基数排序能「更快」的原因——它根本不做比较，所以不受这个下界约束。

手算模板

由中间序列判断算法（本节最高频的综合题）：

  1. 先看有没有元素已在最终位置。
    • 两端各有一段已就位 → 冒泡 / 简单选择 / 堆排序。
    • 中间有一个元素左边全小右边全大 → 快速排序。
  2. 看前缀是否有序但位置不对 → 直接插入排序。
  3. 看是否相隔固定距离成对有序 → 希尔排序，距离就是增量。
  4. 看是否成段有序且段长为 → 归并排序。
  5. 用候选算法手推一趟验证。

由需求选算法：

需求选择
小、记录信息量大简单选择排序（移动少）
小、记录信息量小直接插入排序
大、关键字随机快速排序
大、要省空间 / 怕最坏情况堆排序
大、要求稳定归并排序
初始基本有序直接插入或冒泡
只能链式存储直接插入 / 冒泡 / 简单选择 / 归并 / 基数

边界

说法判断说明
「冒泡和简单选择的最好情况都是 」❌简单选择与初始状态无关，恒为
「希尔排序的时间复杂度是 」⚠️教材不给具体值，表里那三格是空的
「快速排序的空间是 」❌，最坏
「 的稳定算法有归并和堆」❌只有归并
「堆排序的空间比快排大」❌堆排序 更少（8.6.2 原话）
「快速排序是最好的排序算法」⚠️限定：关键字随机分布时、基于比较的内部排序算法中
「初始基本有序时用快速排序」❌此时快排最坏；应选直接插入或冒泡
「 小时一律用直接插入排序」❌记录本身信息量大时用简单选择排序（移动次数少）
「堆排序适用于链式存储」❌仅顺序存储
「归并排序只能用于顺序存储」❌顺序和链式都可以
「基数排序也受 下界约束」❌它不基于比较，不受该下界约束
「稳定的算法比不稳定的好」❌稳定性不衡量优劣（8.1.1）

口径差异：

算竞里排序只有一个动作：sort()；需要稳定就 stable_sort()。 408 这一节的全部内容——八行表格、四类分组、过程特征——在算竞里都不产生任何决策。 但它是第 8 章分值最集中的地方：表 8.1 每一格都被单独考过。 建议把这张表默写三遍，比读三遍有用得多。

对照速查

记忆抓手内容
最好能到 的直接插入、冒泡（都要「基本有序」）
与初始状态无关的简单选择、堆排序、归并排序、基数排序
最坏会退化的快速排序（）
空间不是 的快排 、归并 、基数
稳定的四个插入、冒泡、归并、基数
仅顺序存储的四个折半插入、希尔、快排、堆排序
每趟产生极值的三个冒泡、简单选择、堆排序

两句一字不差的结论：

  • 「平均时间复杂度为 的稳定排序算法只有归并排序。」
  • 「当待排序的关键字随机分布时，快速排序被认为是目前基于比较的内部排序算法中最好的算法。」

考点

  • 表 8.1 全表——每一格都被单独考过。
  • 各种排序算法的特点、比较和适用场景（2017、2020、2022 命题追踪）。
  • 排序算法的稳定性判断及改进（2021、2023 命题追踪）。
  • 更适合采用顺序存储的排序算法（2017 命题追踪）。
  • 根据排序的中间过程判断所采用的排序算法（2009、2010 命题追踪）。
  • 每趟排序后都至少能确定一个元素的最终位置的排序算法（2012 命题追踪）。
  • 选取排序算法时需要考虑的因素（2019 命题追踪）。
  • 排序算法小结的四条选择建议。

链接

反向链接