考研笔记

数据结构 第 8 章 名词库

每条最多四行：是／不是／易混／范围。

建设进度：✅ 8.1 排序概念　✅ 8.2 插入排序　✅ 8.3 交换排序　✅ 8.4 选择排序　✅ 8.5 归并/基数/计数　✅ 8.6 比较与应用　✅ 8.7 外部排序　（全章完整）

8.1 排序的基本概念

排序

  • 是：重新排列表中的元素，使表中的元素满足按关键字有序的过程。
  • 范围：输出是输入序列的一个重排，使 。

稳定性

  • 是：关键字相同的两个元素，排序前后相对次序不变。
  • 不是：不能用来衡量算法优劣，只是对算法性质的描述。
  • 范围：关键字不允许重复时，稳定与否无关紧要；证明不稳定只需举一组反例。

内部排序 / 外部排序

  • 是：按元素是否完全存放在内存中划分。
  • 范围：内部排序的两种基本操作是比较和移动；基数排序不基于比较。
  • 易混：不是按数据量大小划分。

8.2 插入排序

直接插入排序

  • 是：把待排记录按关键字插入前面已排好序的子序列。
  • 范围：最好 、平均/最坏 、空间 、稳定、顺序和链式都适用。

折半插入排序

  • 是：用折半查找定位插入位置，然后统一后移。
  • 不是：总时间复杂度不是 ，仍是 。
  • 范围：只减少比较次数（约 且与初始状态无关）；移动次数未变；稳定；仅适用于顺序存储。

希尔排序

  • 是：也称缩小增量排序，按增量分组做直接插入排序，直到 。
  • 不是：教材不给具体的时间复杂度——「依赖于增量函数，无法准确给出」。
  • 范围：空间 、不稳定、仅顺序存储；尚未求得一个最好的增量序列。

8.3 交换排序

冒泡排序

  • 是：两两比较相邻元素，逆序则交换；每趟确定一个元素的最终位置。
  • 范围：最好 （带提前结束判断）、平均/最坏 、空间 、稳定、顺序+链式。

快速排序

  • 是：基于分治，一次划分把枢轴放到最终位置。
  • 范围：最好/平均 、最坏 （序列已有序时）、空间 （递归工作栈，最坏 ）、不稳定、仅顺序存储。
  • 易混：空间不是 ； 的是堆排序。

教材版 Partition

  • 是：pivot=K[j]（区间最后一个）、填坑而非 swap、先 i 向右再 j 向左、<= 前进 >= 后退。
  • 范围：「一趟划分后的序列」答案唯一，必须照这一版走；算竞的对撞交换法会得到不同的中间序列。

8.4 选择排序

简单选择排序

  • 是：第 趟从 中选最小的与 交换。
  • 不是：最好情况也不是 。
  • 范围：比较次数恒为 ，与初始状态无关，时间始终 ；移动不超过 次；不稳定（反例 ）；顺序和链式都适用。

堆

  • 是： 且 （大根堆），。
  • 范围：可视为完全二叉树；大根堆的最大元素在根，任意非根结点的值小于或等于其双亲结点值。
  • 易混：不同分支的结点之间没有大小关系。

建堆

  • 是：从 往前，逐个对以该结点为根的子树筛选。
  • 范围：大根堆调整时与左右孩子中较大者交换；交换后可能连锁下沉，要一路调到底；建堆是线性时间 。

堆排序

  • 是：建堆 → 输出堆顶 → 堆底元素送堆顶 → 向下调整 → 重复。
  • 范围：最好/平均/最坏都是 ；空间 （三个 算法里最省）；不稳定；仅顺序存储。

堆的应用

  • 是：只有两个——堆排序和优先队列（大纲新增考点，教材明确限定）。

8.5 归并、基数、计数

二路归并排序

  • 是：把 个长度为 1 的有序表两两归并，直至合成一个长度为 的有序表。
  • 范围：分割子序列与初始序列的排列无关，所以最好/最坏/平均都是 ；空间 ；稳定；顺序+链式；归并趟数 。
  • 易混：平均时间复杂度为 的稳定排序算法只有它一个。

基数排序

  • 是：不基于比较和移动，基于关键字各位的大小，通过分配和收集实现。
  • 范围：（三种情况相同）；空间 （与 无关）；稳定（且稳定是 LSD 正确性的前提）；顺序+链式。

计数排序

  • 是：统计比每个元素小的元素个数，直接定位。
  • 范围：教材标 *8.5.3，选学；比较写成 if(a[i]<=a[j]) count[j]++; 才稳定，少一个等号就不稳定。

8.6 比较与应用

表 8.1

  • 范围：希尔排序的三个时间格子是空的（依赖增量函数）；空间那一列仅列举平均情况（快排最坏 未写在表里）。

稳定的四个 / 不稳定的四个

  • 是：稳定 = 插入、冒泡、归并、基数；不稳定 = 简单选择、快速、希尔、堆。
  • 范围：教材建议从算法原理上理解，而不应拘泥于死记硬背。

仅顺序存储的四个

  • 是：折半插入、希尔、快速、堆排序。
  • 范围：共同原因是都需要随机存取；其余五个（直接插入、冒泡、简单选择、归并、基数）顺序和链式都适用。

过程特征

  • 是：冒泡、简单选择、堆排序每趟产生当前最大或最小值；快速排序一趟至少确定一个元素的最终位置。
  • 范围：这是「给中间序列问算法」这类题的判据。

排序算法小结

  • 是： 小用直接插入或简单选择（记录信息量大时用简单选择，移动少）； 大用快排/堆/归并（要稳定选归并）；初始基本有序选直接插入或冒泡。
  • 范围：「快排最好」的限定语是**「关键字随机分布时、基于比较的内部排序算法中」**。

8.7 外部排序

外部排序

  • 是：待排文件无法一次装入内存，需要在内存和外存之间多次交换数据的排序。
  • 范围：时间代价主要考虑 I/O 次数；教材明说不会在算法设计上进行考查。

归并段（顺串）

  • 是：第一阶段由内部排序产生的有序子文件。
  • 范围：个数记为 ，长度记为 ，。

归并趟数

  • 是：， 为归并路数。
  • 范围：总 I/O 次数 ， 为磁盘块数；末尾那个 是内部排序阶段的读/写，最容易漏。

多路平衡归并

  • 是：每趟把 个（或不足 个）有序段归并为一个。
  • 范围：增大 减少趟数，但内部比较随 增长；且缓冲区变小会使交换次数增大，所以 不是越大越好。

败者树

  • 是：树形选择排序的一种变体，可视为完全二叉树； 个叶结点存各段当前元素，内部结点记忆左右子树中的「失败者」。
  • 不是：根 ls[0] 存的是冠军的段号，不是败者。
  • 范围：深度 ；选一次最小仅需 次比较；初始构造需 次比较；使用后内部归并的比较次数与 无关。

置换-选择排序

  • 是：用工作区 WA 反复选 MINIMAX 记录输出，产生长度超过 WA 容量的初始归并段。
  • 范围：MINIMAX 是**「比上一个输出值大的记录中的最小者」；选不出新 MINIMAX 时当前归并段结束；教材说选 MINIMAX 的过程需利用败者树实现**。

最佳归并树

  • 是：把哈夫曼树推广到 叉，让记录数少的归并段最先归并，使总 I/O 最少。
  • 范围：I/O 次数 ；WPL 内部结点权值。

虚段

  • 是：初始归并段不足以构成严格（正则） 叉树时补入的、长度为 0 的段。
  • 范围：； 时补 个；权为 0 的叶子应离树根最远。
  • 易混：「缺额的归并段留在最后做低路归并」不是最佳方案（教材例中 386 > 326）。

高频范围限定清单

常见说法范围限定
「稳定的算法更好」错。稳定性不衡量优劣
「关键字不重复时也要考虑稳定性」错。无关紧要
「所有内部排序都基于比较」错。基数排序不基于比较
「折半插入排序总时间 」错。只是比较次数；总时间仍
「折半插入的比较次数与初始状态有关」错。无关，仅取决于
「折半插入可用于链表」错。仅顺序存储
「直接插入只能用于顺序表」错。顺序和链式都行
「希尔排序时间是 」教材不给具体值，表里是空格
「冒泡最好 」错。带提前结束判断时是
「简单选择最好 」错。比较次数恒为
「快排空间 」错。，最坏
「快排最坏 」错。，序列已有序时
「快排对有序序列最快」错。此时划分最不平衡
「枢轴随便取，中间序列一样」错。教材版枢轴是区间最后一个、用填坑法
「一趟快排所有元素到位」错。至少一个（枢轴）到位
「建堆从 开始」错。从 往前
「建堆时间 」错。线性时间
「大根堆与左孩子交换」错。与左右孩子中较大者
「一次交换即完成调整」错。可能连锁下沉
「堆排序空间 」错。
「堆的应用有很多」错。只有堆排序和优先队列
「归并最坏 」错。三种情况都是
「归并空间 」错。
「 稳定算法有好几个」错。只有归并排序
「基数排序空间 」错。
「基数排序可以不稳定」错。稳定是 LSD 正确性的前提
「基数排序受 下界约束」错。它不基于比较
「计数排序天然稳定」错。取决于比较时有没有等号
「堆排序空间比快排大」错。堆 更省
「初始基本有序用快排」错。用直接插入或冒泡
「 小一律用直接插入」错。记录信息量大时用简单选择
「外部排序会考算法设计」错。教材明说不会
「归并趟数 」错。
「总 I/O 」错。还要加内部排序阶段的
「增大 一定更快」错。 过大时缓冲区变小，读/写反而增加
「败者树内部结点存胜者」错。存败者；ls[0] 存冠军
「初始建败者树需 次比较」错。 次
「败者树深度 」错。
「二路归并只要两个缓冲区」错。三个：两输入一输出
「MINIMAX 是 WA 中最小值」只在段首成立；段中是「比上一个输出值大的最小者」
「I/O 次数 = WPL」错。
「虚段可放在任意位置」错。权为 0 的叶子应离根最远
「缺额留最后做低路归并即可」错。不是最佳方案

链接

反向链接