考研笔记

归并排序、基数排序和计数排序

这三个算法在表 8.1 里占了两个「稳定」和唯一一个「非比较」的位置。

  • 归并排序：唯一一个平均 且稳定的算法。
  • 基数排序：唯一一个不基于比较的算法（8.1 原话）。
  • 计数排序：教材标为 *8.5.3，选学内容。

机制

归并排序

「归并」的含义是将两个或两个以上的有序表组合成一个新的有序表。 二路归并排序把待排序表看成 个长度为 1 的有序表，两两归并得到 个长度为 2（最后一个可能为 1）的有序表；继续两两归并……如此重复，直到合并成一个长度为 的有序表为止。

教材对它的评价（8.6.1 原话）：

归并排序同样基于分治的思想，但其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 。

边界辨析：

「分割与初始序列无关」是归并与 快速排序 的根本差别。 快排的分割点是枢轴的实际落位，取决于数据，所以最坏会退化成 ； 归并永远从中间对半切，三种情况一样快。 代价写在 8.6.1 里：「二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为 ， 虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。」

指标值
最好 / 平均 / 最坏时间都是
空间
稳定性稳定
适用存储顺序 + 链式
归并趟数

归并排序是「平均时间复杂度为 的稳定排序算法中唯一的一个」（8.6.1 原话：「平均时间复杂度为 的稳定排序算法只有归并排序」）。这句话是选择题的直接答案来源。

基数排序

基数排序不基于比较和移动进行排序，而基于关键字各位的大小进行排序。它借助多关键字排序的思想，通过**「分配」和「收集」**两种操作对单逻辑关键字进行排序。

设长度为 的线性表中每个结点 的关键字由 元组 组成，其中每位取值范围为 ， 称为基数。

最低位优先（LSD）：从最低位关键字 开始，每一趟做一次「分配 + 收集」，共 趟。

指标值
最好 / 平均 / 最坏时间都是
空间
稳定性稳定
适用存储顺序 + 链式

边界辨析：

基数排序的稳定性不是可选项，而是正确性的前提。 LSD 每一趟都必须保持前一趟的相对次序， 否则低位排好的结果会被高位那一趟打乱。「基数排序必须稳定」和「基数排序是稳定的」是同一件事的两面。

另外注意 空间是 不是 ——占空间的是 个队列（桶）的头尾指针，不是数据本身。 表 8.1 里它是唯一一个空间与 无关的算法。

计数排序（* 选学）

教材把 8.5.3 标为 *8.5.3，属于选学或降低要求的内容。

基本思想：对每个元素 ，统计小于 的元素个数，从而直接确定 在有序序列中的位置。教材 8.5 的试题解析里给了一段 cmpCountSort：count 数组记录比对应待排序数组元素下标大的元素个数，例如 count[1]=3 意思是数组 a 中有三个元素比 a[1] 小，即 a[1] 是第四大元素，a[1] 的正确位置应是 b[3]。

边界辨析：

教材试题解析里有一条稳定性的关键细节： 用 for(i=0;i<n-1;i++) 和 for(j=i+1;j<n;j++) 两两比较时，总比较次数是 ； 而要让它稳定，必须把判断写成

if(a[i]<=a[j]) count[j]++;
else           count[i]++;

「若不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，则导致原序列中靠前的元素在排序后的序列中处于靠后的位置。」 ——一个等号决定稳定与否，这是本节最精细的一条。

手算模板

归并排序的每一趟：把当前的有序段两两合并。第 趟后，每段长度为 （最后一段可能不足）。共 趟。

基数排序的每一趟：

  1. 看当前位（第一趟看最低位）。
  2. 分配：按该位的值把元素依次放进 个桶（队列），入队顺序就是当前序列的顺序。
  3. 收集：从 0 号桶到 号桶依次出队，接成新序列。
  4. 换下一位，回到第 1 步，共 趟。

验算：第 趟后，序列按最低 位有序。

边界

说法判断说明
「归并排序最坏 」❌三种情况都是
「归并排序空间 」❌，需要辅助数组做元素复制
「归并排序不稳定」❌稳定
「 的稳定算法有好几个」❌只有归并排序
「归并排序只能用于顺序存储」❌顺序和链式都可以
「基数排序基于比较」❌不基于比较，是全章唯一
「基数排序空间 」❌， 是基数
「基数排序时间是 」❌，与 近似线性
「基数排序可以不稳定」❌必须稳定，否则 LSD 的结果是错的
「基数排序适用于任意关键字」⚠️需要关键字能拆成 位、每位取值在
「计数排序是重点」❌教材标 *，选学内容
「计数排序天然稳定」❌取决于比较时有没有等号

口径差异：

算竞里归并排序主要用来求逆序对，基数排序几乎只在卡常时出现，计数排序则是值域小时的常规操作。 408 一个都不这么考。 它考的是三张表里的格子：时间三档、空间、稳定性、适用存储。 尤其「归并是唯一 稳定算法」「基数是唯一非比较算法」「基数空间 」这三条， 在算竞视角里都是无关紧要的细节，在 408 里是直接的选择题答案。

对照速查

算法最好平均最坏空间稳定存储
二路归并是顺序 + 链式
基数排序是顺序 + 链式
唯一性结论内容
唯一 的稳定算法归并排序
唯一不基于比较的算法基数排序
唯一空间与 无关的算法基数排序（）
唯一三种情况时间都相同的比较类算法归并排序（堆排序也是，但它属选择类）

考点

  • 归并排序三种情况时间都是 ，因为分割与初始序列无关。
  • 归并是唯一 的稳定算法。
  • 归并空间 。
  • 基数排序不基于比较，空间 ，时间 。
  • 基数排序必须稳定。
  • 计数排序里等号决定稳定性。

链接

反向链接