考研笔记

排序的基本概念与插入排序

这一节最值钱的是「稳定性」的准确定义，以及教材对它的两句限定。

排序算法你都会写，但 408 考的是教材口径下的三件事：稳定性的定义、每一趟的中间结果、以及适用的存储结构。这三样在算法竞赛里都不产生任何影响，所以这一章要按「补差集」来读，不要重学算法。

机制

排序的定义与稳定性

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

  • 输入： 个记录 ，对应的关键字为 。
  • 输出：输入序列的一个重排 ，使得 （其中「」可以换成其他的比较大小的符号）。

算法的稳定性：若待排序表中有两个元素 和 ，其对应的关键字相同，即 ，且在排序前 在 的前面，若使用某一排序算法排序后， 仍然在 的前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。

边界辨析：

教材紧跟着给了两句限定，两句都能单独出选择题：

  1. 「算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。」 ——稳定 ≠ 更好。 堆排序不稳定但性能优秀。
  2. 「若待排序表中的关键字不允许重复，排序结果是唯一的，则对于排序算法的选择，稳定与否无关紧要。」 ——没有相等关键字时，稳定性这个概念本身就失去意义。

另有注意框：「对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。」 证明不稳定只需要一个反例，不需要论证。

内部排序与外部排序

在排序过程中，根据数据元素是否完全存放在内存中，可将排序算法分为两类：

类别定义
内部排序排序期间元素全部存放在内存中的排序
外部排序排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较操作。

通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类。

教材注意框：「大多数的内部排序算法都更适用于顺序存储的线性表。」

直接插入排序

每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

指标值
最好时间（表已正序）
平均 / 最坏时间
空间
稳定性稳定
适用存储顺序存储和链式存储都可以

折半插入排序

因为是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就统一地向后移动元素。

void InsertSort(ElemType A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){                  //依次将 A[2]~A[n] 插入前面的已排序序列
        A[0]=A[i];                      //将 A[i] 暂存到 A[0]
        low=1;high=i-1;                 //设置折半查找的范围
        while(low<=high){               //折半查找（默认递增有序）
            mid=(low+high)/2;
            if(A[mid]>A[0]) high=mid-1; //查找左半子表
            else            low=mid+1;  //查找右半子表
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];                //统一后移元素，空出插入位置
        A[high+1]=A[0];                 //插入操作
    }
}

边界辨析：

教材对折半插入排序的四句话，每一句都是考点：

  1. 「仅减少了比较元素的次数，时间复杂度约为 」——指的是比较的次数。
  2. 「该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 」——与直接插入排序的关键差别。
  3. 「元素的移动次数并未改变，它依赖于待排序表的初始状态」，因此总的时间复杂度仍为 。
  4. 「折半插入排序仅适用于顺序存储的线性表。」

所以折半插入排序不比直接插入排序快一个量级，只是常数更优。 它是稳定的。

希尔排序

也称缩小增量排序。基本思想：先将待排序表分割成若干形如 的「特殊」子表，即把相隔某个「增量」的记录组成一个子表，对各个子表分别进行直接插入排序；当整个表中的元素已呈「基本有序」时，再对全体记录进行一次直接插入排序。

过程：先取一个小于 的增量 ，把表中的全部记录分成 组，所有距离为 的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个增量 ，重复上述过程，直到所取到的 ，即所有记录已放在同一组中，再进行一趟直接插入排序。

指标值
时间依赖于增量函数，无法准确给出（教材原话）
空间
稳定性不稳定
适用存储仅顺序存储

边界辨析：

「到目前为止，尚未求得一个最好的增量序列。」 所以表 8.1 里希尔排序的时间复杂度那三格是空的—— 教材明说「因为希尔排序的时间复杂度依赖于增量函数，所以无法准确给出其时间复杂度」。 看到选项写「希尔排序的时间复杂度为 」要小心：那是某个特定增量序列下的经验值， 王道正文没有给这个结论。考试问「希尔排序的时间复杂度」时，安全答案是「与增量序列有关」。

口径差异：

算竞里几乎不写插入排序族（std::sort 内部会在小区间用插入排序，但那是库的事）， 更不会关心「折半插入减少的是比较还是移动」。 408 恰恰把这个区分单独拎出来考（2012 命题追踪：直接插入排序和折半插入排序的比较）。 希尔排序在算竞里更是绝迹，但 408 反复考「根据中间过程判断所采用的增量」（2014、2018）—— 这是纯手算题，只能按教材的分组规则一步步走。

手算模板

直接插入排序的一趟：第 趟处理 ，把它插进 的正确位置。第 趟结束后，前 个元素有序（但不一定在最终位置）。

希尔排序的一趟：

  1. 按增量 把下标分组：、……共 组。
  2. 每组内部做直接插入排序（组内元素在原数组中隔 个位置）。
  3. 写出这一趟后的整个数组。

由中间结果反推增量：看哪些位置的元素发生了「远距离交换」，距离就是增量。若某一趟后整体只是局部有序、且相隔 的位置成对有序，则该趟增量为 。

边界

说法判断说明
「稳定的排序算法更好」❌稳定性不能衡量算法优劣，只是对性质的描述
「关键字不重复时也要考虑稳定性」❌稳定与否无关紧要
「证明不稳定需要一般性论证」❌举一组反例即可
「所有内部排序都基于比较」❌基数排序不基于比较
「内部排序 / 外部排序按数据量分」❌按元素是否完全存放在内存分
「折半插入排序的时间复杂度是 」❌比较次数是；总时间仍是 ，因为移动没变
「折半插入排序的比较次数与初始状态有关」❌无关，仅取决于
「折半插入排序不稳定」❌稳定
「折半插入排序可用于链表」❌仅适用于顺序存储
「直接插入排序只能用于顺序表」❌顺序和链式都可以
「希尔排序的时间复杂度是 」⚠️教材说依赖增量函数，无法准确给出
「希尔排序稳定」❌不稳定
「希尔排序最后一趟增量可以不是 1」❌必须取到

对照速查

算法最好平均最坏空间稳定存储
直接插入是顺序 + 链式
折半插入—是仅顺序
希尔无法准确给出否仅顺序
折半插入改变了什么结论
比较次数减少到约 ，与初始状态无关
移动次数未改变，依赖初始状态
总时间复杂度仍为

考点

  • 稳定性的定义及两句限定（不衡量优劣、关键字唯一时无关紧要）。
  • 基数排序不基于比较。
  • 折半插入排序减少的是比较不是移动（2012 命题追踪）。
  • 折半插入排序的比较次数与初始状态无关。
  • 希尔排序的时间复杂度依赖增量序列，教材不给具体值。
  • 根据希尔排序的中间过程判断所采用的增量（2014、2018 命题追踪）。
  • 希尔排序中各子序列采用直接插入排序（2015 命题追踪）。

链接

反向链接