🎯 408 排序与查找核心速查笔记

核心痛点解决

面对题目想不起算法?本笔记按照 408 考察频率 排序。 【口诀 + 可折叠手算例子 + 代码骨架 + 变体预警】,让你不仅看懂,还能手算,更能在考场上秒杀。


📊 一、排序算法(按考察频率排序)

1. 快速排序(Quick Sort)—— 考察频率:⭐⭐⭐⭐⭐

一句话记忆

“挖坑填数 + 分治”。选一个基准(Pivot),把比它小的扔左边,比它大的扔右边,然后递归左右两边。

代码骨架(手写题必背)

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;
}

变体预警:快排“趟数”与基准归位数量模型(408 核心命题雷区)

  1. 统考“一趟(Pass)”的严格定义:
    • 408 统考真题官方定义:“对尚未确定最终位置的所有元素进行一遍处理称为一趟”。
    • 也就是说,上一趟划分出来的所有非空子序列,在下一趟中都必须各自独立执行一次 Partition!
  2. 第二趟结束到底有几个元素归位?—— 牢记“两端出 2 个,中间出 3 个”分支模型:
    • 情况 ①:第 1 趟基准落在【最左端 / 最右端】(极端划分)
      • 只能切出 1 个非空子序列,第 2 趟只对该子序列做 1 次 Partition;
      • 第二趟结束后:全局恰好有 2 个 基准元素归位(且必有 1 个处于整序列的最左端或最右端!)。
    • 情况 ②:第 1 趟基准落在【中间位置】(正常划分)
      • 切出左、右两个非空子序列,第 2 趟必须对左边和右边分别再跑一次 Partition;
      • 第二趟结束后:全局必定有 3 个 基准元素归位!
    • ⚠️ 秒杀排查死穴:若选项中归位元素只有 2 个,但这两个基准全都在中间,端点一个都没有,说明至少有一侧的子序列被“漏排”了,绝对不可能是第二趟结果,直接秒杀!
  3. 基准归位位置特征:
    • 快速排序是所有内部排序中,唯一一个每趟能把一个中间位置(不一定是最大/最小端)元素放到最终位置上的算法(冒泡、简单选择、堆排序每趟都是让最值归位到两端)。


2. 堆排序(Heap Sort)—— 考察频率:⭐⭐⭐⭐

一句话记忆

“升序建大根堆,降序建小根堆;堆顶与末尾交换,然后向下调整(Shift Down)”。

代码骨架(Shift Down,下标从 1 开始)

void AdjustDown(int A[], int k, int len) {
    A[0] = A[k]; // 暂存当前根节点
    for (int i = 2*k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i+1]) i++; // 取左右孩子中较大的
        if (A[0] >= A[i]) break; // 根节点已大于等于最大孩子,满足大根堆
        else { A[k] = A[i]; k = i; } // 大孩子上浮,继续往下看
    }
    A[k] = A[0];
}

3. 归并排序(Merge Sort)—— 考察频率:⭐⭐⭐⭐

一句话记忆

“分治 + 合并两个有序表,辅助空间 O(n)”。

代码骨架(Merge)

void Merge(int A[], int low, int mid, int high) {
    int i = low, j = mid+1, k = 0;
    int *B = (int*)malloc((high-low+1)*sizeof(int));
    while (i <= mid && j <= high) {
        if (A[i] <= A[j]) B[k++] = A[i++]; // <= 保证稳定性:相等时先取左表
        else B[k++] = A[j++];
    }
    while (i <= mid) B[k++] = A[i++];
    while (j <= high) B[k++] = A[j++];
    for (k = 0, i = low; i <= high; i++, k++) A[i] = B[k];
    free(B);
}

4. 希尔排序(Shell Sort)—— 考察频率:⭐⭐⭐

一句话原理与生活映射

“跳着分组抓扑克,增量逐渐缩到 1”。 直接插入排序在基本有序时效率极高(可达 )。希尔排序正是利用了这一点:先用较大的步长 (增量)把相隔距离为 的元素划为一组,在各组内部独立进行直接插入排序,让整个序列在宏观上迅速变得“大致有序”;随后不断缩小增量 ,直到最后一趟 时做全局直接插入排序,由于前面做了深度预处理,最后一趟几乎无需过多挪位即可秒排完成!

核心性能与考点预警(408 必背四绝)

  1. 稳定性:不稳定!相同元素若被分在不同子组内,各自组内排序后相对先后位置极易颠覆。
  2. 仅适用于顺序存储(数组):必须依赖下标随机访问(通过 i + d 定位),链表绝对不能高效使用希尔排序!
  3. 最后一趟增量必须为 1(即 ),只有 才能收敛保证全局完全有序。
  4. 时间与空间复杂度:空间复杂度 (原地排序);时间复杂度在特定增量序列下约为 ,最坏情况为 。

5. 直接插入排序(Insert Sort)与折半插入排序 —— 考察频率:⭐⭐⭐

一句话原理与生活映射

“理顺手里的扑克牌”。 将数组划分为 “前面已排序区” 与 “后面未排序区”。每次从未排序区抓起第一张牌(放入暂存哨兵),从后往前在已排序区逐个比对:只要发现比新牌大,就统统往后挪一格腾位置;一旦遇到小于等于它的牌,立刻插进去!

核心性能底层特征(408 重点命题点)

  1. 比较次数与初始状态极度敏感:
    • 最好情况(已有序):每趟只需与前一个元素比 1 次,比较次数仅需 次,时间复杂度达 !
    • 最坏情况(逆序):每趟都要比到头,比较次数达 次,时间复杂度 。
  2. 移动次数:已有序时移动 0 次;逆序时每次都要全部后移,移动次数同样为 。
  3. 空间复杂度:,仅需常数级辅助单元(哨兵 A[0])。
  4. 稳定性:稳定。因为比对条件是 A[0] < A[j],相等时不后移,相对顺序永远不变。
  5. 折半插入排序(Binary Insert Sort)辨析:
    • 利用有序表中折半查找加速“寻找插入位置”,比较次数锐减为 ;
    • 但元素后移次数丝毫不变(依然是 ),故总时间复杂度依然是 ,且只能用于顺序存储!

6. 简单选择排序(Simple Selection Sort)—— 考察频率:⭐⭐⭐

一句话原理与生活映射

“擂台选秀,定点交换”。 同样划分“已排序区”和“未排序区”。但它的策略是:绝不频繁挪动!每一趟只身深入未排序区,从头扫到尾把所有人逐个比一遍,锁定其中的全局最小值,然后只与未排序区的第一个元素交换一次位置。

核心性能底层特征(408 绝命陷阱)

  1. 比较次数与初始状态完全无关,恒为 次!
    • 不管给你的序列是已经排好序、逆序还是乱序,每次选擂主必须把剩下的元素一个不漏全部比一遍才能确认是不是最小,因此无论最好、最坏还是平均,比较次数恒为 。
  2. 移动次数极少:
    • 最好情况(已有序)移动 0 次;
    • 最坏情况每趟交换 1 次(每次交换 3 次移动),总移动次数至多 次,移动开销仅为 。
  3. 空间复杂度:,原地排序。
  4. 稳定性:不稳定!
    • 典型反例:序列 [2, 2*, 1],第一趟选出最小值 1 与首个元素 2 交换,得到 [1, 2*, 2],两个 2 的相对先后次序被不可逆颠覆!

7. 冒泡排序(Bubble Sort)—— 考察频率:⭐⭐⭐

一句话原理与生活映射

“水底气泡,大者上浮”。 每一趟从左向右两两比较相邻元素,只要前一个比后一个大就交换位置,一趟走完把未排序区的最大值一路护送到最右端。

核心性能特征

  • 时间复杂度:最好 (已完全有序,仅跑一趟比较 次),最坏 (逆序),平均 。
  • 空间复杂度:,原地排序。
  • 稳定性:稳定。相邻两两比较,相等时不发生交换,相同元素相对次序保持不变。

8. 基数排序(Radix Sort)—— 考察频率:⭐⭐⭐

一句话原理与生活映射

“按位装桶,先进先出”。 唯一一种不基于关键字相互比较的排序法。每一趟按照某一位(个位、十位、百位)的数值,将元素丢入 个桶(队列)中(分配),再按桶的标号由小到大首尾串联倒出来(收集)。

核心性能特征(408 计算题考点)

  • 时间复杂度:,其中 为关键字位数(趟数), 为元素个数, 为基数(十进制为 10)。
  • 空间复杂度:,需要 个队列的头、尾指针。
  • 稳定性:稳定。先进先出的队列维护了相同数位元素的相对次序。

9. ⚔️ 巅峰对决与真题剖析:直接插入 vs 简单选择

核心认知纠偏:直接插入为什么在大致有序时把简单选择按在地上摩擦?

很多同学以为“直接插入要挪元素,选择排序只要交换,所以选择排序快”,这是极具误导性的致命直觉! 计算机执行算法时,比较次数与内存读写是耗时核心。当数组大部分有序时:

  • 直接插入排序是“聪明且懂得摸鱼”的:新元素往左比,一旦发现前一个元素比自己小,立刻 break 停止比对!因此在大部分有序时,平均比 1~2 次就收工,比较总次数暴降到接近 。
  • 简单选择排序是“死板且机械僵化”的:不管你多有序,它必须把剩下所有人从头到尾挨个比完才敢确认谁是最小,永远雷打不动执行 次比较()。

【实战真题演练 · 2020 年 408 第 11 题】

【2020 年 408 统考真题 第 11 题】 对大部分元素已有序的数组进行排序时,直接插入排序比简单选择排序效率更高,其原因是( )

I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需要的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少

A. 仅 I    B. 仅 III    C. 仅 I、II    D. I、II、III

深度三段式逐项排查:

  1. 排查 I(比较次数更少)—— ✅ 完全正确(核心根本原因):
    • 大部分有序时,直接插入每次内层循环比 1 次就终止,比较次数从逆序的 骤降至 ;
    • 简单选择排序的比较次数与初始序列状态毫无关系,永远固定为 。故直接插入的比较次数远少于简单选择,I 正确!
  2. 排查 II(所需辅助空间更少)—— ❌ 彻底错误(两者完全相同):
    • 两者均为原地排序(In-place sort),只需要单个常数级临时变量(temp 或哨兵 A[0]),辅助空间均为 。没有任何谁多谁少之分,II 错误!
  3. 排查 III(元素的移动次数更少)—— ❌ 彻底错误(命题人最大的迷魂阵):
    • 简单选择排序每趟最多只交换一次(总移动次数顶多 次,是极其节省移动操作的算法);
    • 反观直接插入排序,只要遇到无序零头,为了给新元素挪出位置,需要将前序元素逐个往后搬移。在非完全有序(即“大部分有序”)的一般情况下,直接插入的移动次数完全不比简单选择排序少,甚至往往更多!故 III 绝不是直接插入效率更高的原因,III 错误!

考场 5 秒速记对比表:

算法维度直接插入排序(Insert Sort)简单选择排序(Selection Sort)差异本质与胜负判定
底层运作哲学“插牌腾位,遇小即停”“全员比擂,一趟换一”直接插入懂提前停,简单选择死板比完全程
元素比较次数与初始状态强相关
最好 ,最坏
与初始状态完全无关
恒为
🏆 大部分有序时直接插入比较次数极少(完胜)
元素移动次数取决于逆序对数,需要后移腾位
最好 ,最坏
仅在选出最小值后交换一次
至多 次()
⚠️ 简单选择移动通常更少,直接插入不占优
辅助空间原地排序 原地排序 🤝 平手,毫无差异
算法稳定性✅ 稳定(相同元素不挪位)❌ 不稳定(跨越交换破坏先后次序)🏆 直接插入稳定

🔍 二、查找算法速览(折半查找)

折半查找核心公式

  • 判定树高度(即查找成功或失败的最多比较次数):(或 )。
  • 判定树性质:折半查找判定树是一棵平衡二叉树(AVL 树),且中序遍历必定递增有序。若 mid = ⌊(low+high)/2⌋(向下取整),则对于任何一个节点,其右子树节点数 - 左子树节点数 = 0 或 1(右大于等于左)!

📋 三、稳定性与复杂度速查表(重点背诵)

稳定性与适用存储结构口诀

  • 不稳定口诀:“快些选堆,不稳定”(快速、希尔、简单选择、堆排序)。
  • 比较次数与初始状态无关:“选基二归”(简单选择、基数、二路归并)。
  • 排序趟数与初始状态有关:“快泡”(快速排序递归深度/趟数取决于枢轴划分是否均匀;冒泡排序可提前结束)。
算法名称最好时间平均时间最坏时间空间复杂度稳定性适用链表?
直接插入✅ 稳定✅ 可用于链表
冒泡排序✅ 稳定✅ 可用于链表
简单选择❌ 不稳定✅ 可用于链表
希尔排序—❌ 不稳定❌ 仅顺序表
快速排序❌ 不稳定❌ 仅顺序表
堆排序❌ 不稳定❌ 仅顺序表
二路归并✅ 稳定✅ 可用于链表
基数排序✅ 稳定✅ 常用链式

📝 四、历年真题精选(实战演练·破局版)

真题 1(折半查找)

题目:对含有 600 个元素的有序顺序表进行折半查找,关键字之间的比较次数最多是( )。 A. 9 B. 10 C. 30 D. 300

真题 2(排序稳定性)

题目:下列排序算法中,不稳定的是( )。 I. 希尔排序 II. 归并排序 III. 快速排序 IV. 堆排序 V. 基数排序 A. 仅 I 和 II B. 仅 II 和 V C. 仅 I, III, IV D. 仅 III, IV, V

真题 3(堆的插入 · 已规范下标推导)

题目:已知序列 [25, 13, 10, 12, 9] 是大根堆,现插入元素 20,调整后得到的新堆是?


📦 五、真题扩展包(外部排序、败者树、置换-选择、最佳归并树)

1. 外部排序与败者树(Loser Tree)—— 考察频率:⭐⭐⭐

核心公式与考点

  1. 外部排序总时间 = 内部排序时间 + 外存信息读写(I/O)时间(主要瓶颈!) + 内部归并比较时间。
  2. 归并趟数:若有 个初始归并段,采用 路平衡归并,则归并趟数 。
  3. 读写磁盘总次数 = 初始生成归并段读写 2 次 + 每趟归并读写 2 次 × S 趟 = 。
  4. 败者树(Loser Tree)的作用:
    • 当增大归并路数 以减少归并趟数 时,内存中每次从 个归并段选最小值的内部比较次数会增加(普通比较需 次)。
    • 引入 路败者树 后,树高(不含最顶上的冠军结点)为 ,每次选出最小元素后的重构只需比较 次,使内部归并时间不再随 的增大而受影响!

2. 置换-选择排序(Replacement Selection)—— 考察频率:⭐⭐

一句话记忆

“利用最小堆生成突破内存容量限制的更长初始归并段,平均长度为 2w”( 为内存工作区大小)。


3. 最佳归并树(K 叉哈夫曼树应用)—— 考察频率:⭐⭐⭐

核心心法(刻在脑子里)

  1. 本质定位:最佳归并树就是 叉哈夫曼树,目标是使整棵树的带权路径长度(WPL)最小,从而让外部排序读写外存的 I/O 次数最少。
  2. 虚段的本质:每进行一次 路归并,都会将 个归并段合成 1 个新段,结点数净减少 个。为保证每次归并都严格凑齐 个段(严格 叉树),若总段数不够,必须在最底层补入权值(长度)为 0 的虚段!
  3. 秒杀公式:若 :
    • 若 :无需补虚段(补 0 个);
    • 若 :需补充虚段个数 。

为什么要补“虚段”?底层推导与直觉记忆

  • 数学推导: 设归并树有 个叶子(初始归并段),加上 个虚段,总叶子数为 。 设非叶结点(归并次数)为 个。在一棵严格 叉树中:
    • 每个非叶结点度数均为 ,总分支数为 ;
    • 总结点数 = 分支数 ,即 ;
    • 整理得: 必须是 的整数倍!
  • 物理意义: 如果段数凑不齐严格 叉,那么必须有一次归并参与的段数少于 。这“少段”的归并必须安排在第一趟(离根最远的最底层)!因为虚段长度为 0,让权值为 0 的虚段在最底层参与合并,能确保所有真实的、权值大的归并段尽可能靠近树根,使总 WPL 达到真正最优!

命题人考场陷阱:公式分母是 而不是 !

  • 很多同学在考场上一紧张写成 或者 ,这是最致命的失分点!
  • 避坑口诀:“分子分母都减 1,余数再被除数减”!
    • 算余数:
    • 算虚段:

408 必考公式:WPL 与 I/O 次数的关系!

  • 最佳归并树的 WPL = 归并过程中的总读记录数 = 总写记录数。
  • 外部排序归并阶段的总 I/O 次数(总读写次数) = !(千万别忘了乘以 2,因为一读一写是 2 次!)