🎯 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; }
📝 小题自测(点击展开看手算)
题目:对数组
[49, 38, 65, 97, 76, 13, 27, 49]进行快速排序(以第一个元素为基准),第一趟划分后的结果是?手算步骤:
- 基准
pivot = 49,挖出A[0],数组变成[坑, 38, 65, 97, 76, 13, 27, 49]。- 右指针 high 先走:从右往左找比 49 小的 →
27填左坑:[27, 38, 65, 97, 76, 13, 坑, 49]。- 左指针 low 再走:从左往右找比 49 大的 →
65填右坑:[27, 38, 坑, 97, 76, 13, 65, 49]。- high 找小:
13填左坑:[27, 38, 13, 97, 76, 坑, 65, 49]。- low 找大:
97填右坑:[27, 38, 13, 坑, 76, 97, 65, 49]。- high 继续往左走与 low 相遇,填回
49。最终结果:
[27, 38, 13, 49, 76, 97, 65, 49]。
变体预警:快排“趟数”与基准归位数量模型(408 核心命题雷区)
- 统考“一趟(Pass)”的严格定义:
- 408 统考真题官方定义:“对尚未确定最终位置的所有元素进行一遍处理称为一趟”。
- 也就是说,上一趟划分出来的所有非空子序列,在下一趟中都必须各自独立执行一次 Partition!
- 第二趟结束到底有几个元素归位?—— 牢记“两端出 2 个,中间出 3 个”分支模型:
- 情况 ①:第 1 趟基准落在【最左端 / 最右端】(极端划分)
- 只能切出 1 个非空子序列,第 2 趟只对该子序列做 1 次 Partition;
- 第二趟结束后:全局恰好有 2 个 基准元素归位(且必有 1 个处于整序列的最左端或最右端!)。
- 情况 ②:第 1 趟基准落在【中间位置】(正常划分)
- 切出左、右两个非空子序列,第 2 趟必须对左边和右边分别再跑一次 Partition;
- 第二趟结束后:全局必定有 3 个 基准元素归位!
- ⚠️ 秒杀排查死穴:若选项中归位元素只有 2 个,但这两个基准全都在中间,端点一个都没有,说明至少有一侧的子序列被“漏排”了,绝对不可能是第二趟结果,直接秒杀!
- 基准归位位置特征:
快速排序是所有内部排序中,唯一一个每趟能把一个中间位置(不一定是最大/最小端)元素放到最终位置上的算法(冒泡、简单选择、堆排序每趟都是让最值归位到两端)。
🎯 【2019 年 408 真题 第 10 题】实战秒杀示范(点击展开) 【题目】
排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是( )。
A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60【解题破局逻辑】
全体元素升序排序目标为:[2, 5, 12, 16, 28, 32, 60, 72](共 8 个元素)。
逐项排查“处于最终位置(其左侧全小、右侧全大)”的基准元素个数与分布:
- A 选项:归位元素为 28(第 5 位)和 72(第 8 位,端点)。
- 合理路径:第 1 趟基准为 72(最右端),第 2 趟对左子序列划分选出 28。共 2 个基准,合法!
- B 选项:归位元素为 2(第 1 位,端点)和 72(第 8 位,端点)。
- 合理路径:第 1 趟基准为 2(最左端),第 2 趟对右子序列划分选出 72。共 2 个基准,合法!
- C 选项:归位元素为 2(第 1 位)、28(第 5 位)、32(第 6 位)。
- 合理路径:第 1 趟基准为 28(中间);第 2 趟对左子序列选出 2,对右子序列选出 32。共 3 个基准,合法!
- D 选项:归位元素仅有 12(第 3 位)和 32(第 6 位)。
- 💥 致命破绽:若第 1 趟基准是 12(位于中间),左侧子序列
[5, 2]和右侧[28, 16, 32, 72, 60]必须在第 2 趟各产生 1 个基准(总共应有 3 个)。但左侧[5, 2]根本没有基准归位,严重违背“一趟”的定义!同理若第 1 趟是 32,右侧也漏排了。故 D 绝对不可能!
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]; }
📝 小题自测(点击展开看手算超细拆解)
题目:对数组
[4, 6, 8, 5, 9]进行堆排序(升序),写出初始建堆的每一步树形变化与调整过程,以及第一趟交换调整后的最终数组。手算步骤(建议在草稿纸上画树,绝不肉眼看数组!):
将数组映射为完全二叉树(1 起始下标):
- 对应关系:根为
A[1]=4;4的左右孩子为A[2]=6, A[3]=8;6的左右孩子为A[4]=5, A[5]=9。4 (1) / \ 6 (2) 8 (3) / \ 5 (4) 9 (5)阶段一:初始建大根堆(从下往上,检查所有非叶子节点):
- 最后一个非叶子节点下标:(元素
6)。调整顺序为:节点 2 节点 1。- 第一步:调整节点 2(值为 6):
- 左右孩子为
5(下标 4)和9(下标 5),较大孩子为9。- 比较父节点
6与较大孩子9:,违反大根堆性质!- 交换 6 与 9:
9上浮到下标 2,6沉到下标 5。节点 5 为叶子,下沉停止。- 此时数组为:
[4, 9, 8, 5, 6]。- 第二步:调整节点 1(值为 4,⚠️ 核心连环下沉):
- 左右孩子为
9(下标 2)和8(下标 3),较大孩子为9。- 比较根节点
4与较大孩子9:,违反大根堆性质!- 第一次交换:
9上浮到堆顶下标 1,4沉到下标 2。- 数组暂为:
[9, 4, 8, 5, 6]。- 【连环下沉检查】:
4来到下标 2 成为新的子树根,必须继续检查其孩子!
- 下标 2 的孩子为
5(下标 4)和6(下标 5),较大孩子为6。- 比较
4与较大孩子6:!- 第二次交换:
6上浮到下标 2,4继续下沉到下标 5。- 下标 5 已是叶子节点,下沉终止!
- 🏆 初始大根堆构建完成:
- 树形:根为
9,左右孩子为6和8;6的孩子为5和4。- 最终初始堆数组:
[9, 6, 8, 5, 4]。阶段二:第一趟排序(交换堆顶与末尾 + 缩小范围向下调整):
- ① 堆顶最大值归位:
- 将堆顶最大元素
A[1]=9与当前堆底A[5]=4交换!- 此时
9归位到下标 5,锁死不再参与后续调整(有效堆大小 )。- 交换后数组:
[4, 6, 8, 5, | 9]。- ② 堆顶 4 向下调整恢复大根堆(仅在有效范围 1~4 内调整):
- 根节点为
4(下标 1),其左右孩子为6(下标 2)和8(下标 3)。- 左右孩子中较大者为
8。- 比较根
4与较大孩子8:!- 交换 4 与 8:
8上浮到堆顶,4沉到下标 3。- 检查下标 3 的孩子:左孩子下标 ,无孩子,调整终止!
第一趟最终结果:
[8, 6, 4, 5, 9](前 4 个元素重新构成大根堆,末尾 9 已是有序区)。[!warning] 变体预警(408 高频考点)
- 建堆时间复杂度是 (比较次数不超过 ),而排序阶段( 次向下调整)时间复杂度是 !千万别把“初始建堆”的时间复杂度误选成 !
- 堆的插入是放到数组末尾后向上调整(Shift Up);堆的删除堆顶是把末尾元素覆盖到堆顶后向下调整(Shift Down)。
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); }
📝 小题自测(点击展开看手算)
题目:对数组
[49, 38, 65, 97, 76, 13, 27, 49*]进行 2 路归并排序(升序)。
- 写出第 1 趟、第 2 趟、第 3 趟归并后的数组状态。
- 两个长度分别为 和 的有序段归并时,最少需要比较几次?最多比较几次?
- 归并排序的稳定性在手算中如何体现?
手算步骤: 初始状态将每个元素看作长度为 1 的独立有序段:
[49] [38] | [65] [97] | [76] [13] | [27] [49*]
- 第 1 趟归并(相邻两两合并,有序段长 1 2):
[49]与[38]归并[38, 49][65]与[97]归并[65, 97][76]与[13]归并[13, 76][27]与[49*]归并[27, 49*]- 第 1 趟结果:
[38, 49, 65, 97, 13, 76, 27, 49*]- 第 2 趟归并(有序段长 2 4):
[38, 49]与[65, 97]归并[38, 49, 65, 97][13, 76]与[27, 49*]归并:
- 比 13 与 27 取 13;比 76 与 27 取 27;比 76 与 49* 取 49*;剩 76 直接抄写
[13, 27, 49*, 76]- 第 2 趟结果:
[38, 49, 65, 97, 13, 27, 49*, 76]- 第 3 趟归并(有序段长 4 8,全局完全有序):
- 将前段
[38, 49, 65, 97]与后段[13, 27, 49*, 76]归并:
- 依次取:
132738;- 【稳定性关键比对】:此时比对前段的
49与后段的49*。由于代码中判定为A[i] <= A[j](带等号),严格优先提取前段的 49!- 随后提取后段的
49*,相同元素的相对物理先后次序被严格保全!- 继续取:
6576剩余97。- 第 3 趟(最终)结果:
[13, 27, 38, 49, 49*, 65, 76, 97]- 408 高频定量考点解答:
- 归并趟数: 趟。
- 有序段合并比较次数公式(必背):
- 最少比较次数: 次(较短段的所有元素全部小于较长段首元素,比完较短段后直接提前结束复制)。
- 最多比较次数: 次(两段元素交替穿插,比到仅剩最后 1 个元素才结束)。
[!warning] 核心性能与考点预警(408 必背)
- 空间复杂度 :所有常用内部排序中,归并排序是唯一辅助空间为 的算法(用于合并时暂存元素的辅助数组
B)。- 比较次数与初始状态无关:属于口诀“选基二归”之一,无论序列正序、逆序还是乱序,每一趟划分与合并树形态完全固定,比较与移动的总时间复杂度恒为 。
- 完美支持链表存储:链表执行归并排序不需要额外开辟 数组空间,只需修改指针方向,空间复杂度可降为 !
4. 希尔排序(Shell Sort)—— 考察频率:⭐⭐⭐
一句话原理与生活映射
“跳着分组抓扑克,增量逐渐缩到 1”。 直接插入排序在基本有序时效率极高(可达 )。希尔排序正是利用了这一点:先用较大的步长 (增量)把相隔距离为 的元素划为一组,在各组内部独立进行直接插入排序,让整个序列在宏观上迅速变得“大致有序”;随后不断缩小增量 ,直到最后一趟 时做全局直接插入排序,由于前面做了深度预处理,最后一趟几乎无需过多挪位即可秒排完成!
📝 小题自测(点击展开看手算)
题目:对数组
[49, 38, 65, 97, 76, 13, 27, 49*, 55, 04]采用增量 进行希尔排序,写出第一趟排序后的详细分组及最终序列。手算步骤:
- 按增量 进行交叉跳跃分组(共 5 组):
- 第 1 组(下标 0, 5):
{49, 13}组内排好为{13, 49}- 第 2 组(下标 1, 6):
{38, 27}组内排好为{27, 38}- 第 3 组(下标 2, 7):
{65, 49*}组内排好为{49*, 65}(注意:49*跳到了49前面,直观展示了不稳定!)- 第 4 组(下标 3, 8):
{97, 55}组内排好为{55, 97}- 第 5 组(下标 4, 9):
{76, 04}组内排好为{04, 76}- 第一趟最终结果:
[13, 27, 49*, 55, 04, 49, 38, 65, 97, 76]- 看一眼就能回想起来的本质:跨步跳跃比较,小元素(如
04, 13)瞬间从队尾大跨步“瞬移”到前排,大元素后移,整体迅速趋近有序。
核心性能与考点预警(408 必背四绝)
- 稳定性:不稳定!相同元素若被分在不同子组内,各自组内排序后相对先后位置极易颠覆。
- 仅适用于顺序存储(数组):必须依赖下标随机访问(通过
i + d定位),链表绝对不能高效使用希尔排序!- 最后一趟增量必须为 1(即 ),只有 才能收敛保证全局完全有序。
- 时间与空间复杂度:空间复杂度 (原地排序);时间复杂度在特定增量序列下约为 ,最坏情况为 。
5. 直接插入排序(Insert Sort)与折半插入排序 —— 考察频率:⭐⭐⭐
一句话原理与生活映射
“理顺手里的扑克牌”。 将数组划分为 “前面已排序区” 与 “后面未排序区”。每次从未排序区抓起第一张牌(放入暂存哨兵),从后往前在已排序区逐个比对:只要发现比新牌大,就统统往后挪一格腾位置;一旦遇到小于等于它的牌,立刻插进去!
📝 小题自测(点击展开看手算每一步)
题目:对数组
[38, 65, 97, 76, 13]进行直接插入排序,演示插入76的完整物理过程。手算步骤:
- 已排序区为
[38, 65, 97],当前待插入元素为76。- 将
76存入哨兵A[0] = 76。- 从右往左比对:
- 与
97比:,97向后挪一格:[38, 65, 空, 97];- 与
65比:,比较立刻终止,不再往前比!- 将
76落入空位:[38, 65, 76, 97]。单趟插入完成。
核心性能底层特征(408 重点命题点)
- 比较次数与初始状态极度敏感:
- 最好情况(已有序):每趟只需与前一个元素比 1 次,比较次数仅需 次,时间复杂度达 !
- 最坏情况(逆序):每趟都要比到头,比较次数达 次,时间复杂度 。
- 移动次数:已有序时移动 0 次;逆序时每次都要全部后移,移动次数同样为 。
- 空间复杂度:,仅需常数级辅助单元(哨兵
A[0])。- 稳定性:稳定。因为比对条件是
A[0] < A[j],相等时不后移,相对顺序永远不变。- 折半插入排序(Binary Insert Sort)辨析:
- 利用有序表中折半查找加速“寻找插入位置”,比较次数锐减为 ;
- 但元素后移次数丝毫不变(依然是 ),故总时间复杂度依然是 ,且只能用于顺序存储!
6. 简单选择排序(Simple Selection Sort)—— 考察频率:⭐⭐⭐
一句话原理与生活映射
“擂台选秀,定点交换”。 同样划分“已排序区”和“未排序区”。但它的策略是:绝不频繁挪动!每一趟只身深入未排序区,从头扫到尾把所有人逐个比一遍,锁定其中的全局最小值,然后只与未排序区的第一个元素交换一次位置。
📝 小题自测(点击展开看手算)
题目:对数组
[49, 38, 65, 97, 49*, 13]进行简单选择排序,写出第一趟的执行细节。手算步骤:
- 初始未排序区为整张表,擂主设为
min = 0(元素 49)。- 依次与后方所有元素比对:
38 < 49(min 改为 1)…最终扫描到13(min 定为 5)。- 扫完全表后,仅执行一次两两交换:
A[0]与A[5]交换!- 第一趟结果:
[13, 38, 65, 97, 49*, 49]。此时最小值13稳固归位。
核心性能底层特征(408 绝命陷阱)
- 比较次数与初始状态完全无关,恒为 次!
- 不管给你的序列是已经排好序、逆序还是乱序,每次选擂主必须把剩下的元素一个不漏全部比一遍才能确认是不是最小,因此无论最好、最坏还是平均,比较次数恒为 。
- 移动次数极少:
- 最好情况(已有序)移动 0 次;
- 最坏情况每趟交换 1 次(每次交换 3 次移动),总移动次数至多 次,移动开销仅为 。
- 空间复杂度:,原地排序。
- 稳定性:不稳定!
- 典型反例:序列
[2, 2*, 1],第一趟选出最小值1与首个元素2交换,得到[1, 2*, 2],两个2的相对先后次序被不可逆颠覆!
7. 冒泡排序(Bubble Sort)—— 考察频率:⭐⭐⭐
一句话原理与生活映射
“水底气泡,大者上浮”。 每一趟从左向右两两比较相邻元素,只要前一个比后一个大就交换位置,一趟走完把未排序区的最大值一路护送到最右端。
📝 小题自测(点击展开看手算)
题目:对数组
[49, 38, 65, 97, 76, 13]进行升序冒泡排序,写出第一趟冒泡排序的详细比较交换过程及最终状态。手算步骤:
- 从左向右两两比对,逆序则交换:
- 比对
49与38:,逆序交换[38, 49, 65, 97, 76, 13];- 比对
49与65:,顺序不交换[38, 49, 65, 97, 76, 13];- 比对
65与97:,顺序不交换[38, 49, 65, 97, 76, 13];- 比对
97与76:,逆序交换[38, 49, 65, 76, 97, 13];- 比对
97与13:,逆序交换[38, 49, 65, 76, 13, 97]。- 第一趟最终结果:
[38, 49, 65, 76, 13, 97]。此时全局最大值97稳稳浮到最右端!- 提前结束判据(408 核心考点):
- 本趟共发生了 3 次交换。若某一趟扫描下来一次交换都没发生(交换标志位 flag == false),说明整张表已完全有序,算法可直接提前终止(此时最好时间复杂度为 )。
核心性能特征
- 时间复杂度:最好 (已完全有序,仅跑一趟比较 次),最坏 (逆序),平均 。
- 空间复杂度:,原地排序。
- 稳定性:稳定。相邻两两比较,相等时不发生交换,相同元素相对次序保持不变。
8. 基数排序(Radix Sort)—— 考察频率:⭐⭐⭐
一句话原理与生活映射
“按位装桶,先进先出”。 唯一一种不基于关键字相互比较的排序法。每一趟按照某一位(个位、十位、百位)的数值,将元素丢入 个桶(队列)中(分配),再按桶的标号由小到大首尾串联倒出来(收集)。
📝 小题自测(点击展开看手算)
题目:对序列
[278, 109, 063, 930, 589, 184, 505, 269]采用最低位优先(LSD)基数排序,写出第一趟(个位)与第二趟(十位)“分配”与“收集”后的序列。手算步骤:
- 第一趟(按个位分配与收集):
- 分配(按个位数入 0~9 号队列):
- 队 0:
930- 队 3:
063- 队 4:
184- 队 5:
505- 队 8:
278- 队 9:
109 -> 589 -> 269(同入队 9 的按先后顺序排队)- 收集(从 0 到 9 号队列依次出队串接):
[930, 063, 184, 505, 278, 109, 589, 269]- 第二趟(按十位分配与收集):
- 分配(按十位数入 0~9 号队列):
- 队 0:
505 -> 109(注意 505 个位排在前面,保持先进先出)- 队 3:
930- 队 6:
063 -> 269- 队 7:
278- 队 8:
184 -> 589- 收集:
[505, 109, 930, 063, 269, 278, 184, 589]- 看一眼就能回想起来的本质:基数排序就是**“个位装桶 倒出串起 十位装桶 倒出串起 百位装桶 倒出串起”!每个桶本质上是一个队列(FIFO),因而天然具有稳定性**。
核心性能特征(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
深度三段式逐项排查:
- 排查 I(比较次数更少)—— ✅ 完全正确(核心根本原因):
- 大部分有序时,直接插入每次内层循环比 1 次就终止,比较次数从逆序的 骤降至 ;
- 简单选择排序的比较次数与初始序列状态毫无关系,永远固定为 。故直接插入的比较次数远少于简单选择,I 正确!
- 排查 II(所需辅助空间更少)—— ❌ 彻底错误(两者完全相同):
- 两者均为原地排序(In-place sort),只需要单个常数级临时变量(
temp或哨兵A[0]),辅助空间均为 。没有任何谁多谁少之分,II 错误!
- 两者均为原地排序(In-place sort),只需要单个常数级临时变量(
- 排查 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
🧠 破局思路 。选 B。
公式
真题 2(排序稳定性)
题目:下列排序算法中,不稳定的是( )。 I. 希尔排序 II. 归并排序 III. 快速排序 IV. 堆排序 V. 基数排序 A. 仅 I 和 II B. 仅 II 和 V C. 仅 I, III, IV D. 仅 III, IV, V
🧠 破局思路 C。
口诀“快些选堆”,对应 I(希尔)、III(快排)、IV(堆排)。选
真题 3(堆的插入 · 已规范下标推导)
题目:已知序列
[25, 13, 10, 12, 9]是大根堆,现插入元素 20,调整后得到的新堆是?🧠 破局思路(按 1 起始下标计算,最不易错)
- 堆插入第一步永远是放到数组末尾(第 6 个位置,下标
i = 6):[25(1), 13(2), 10(3), 12(4), 9(5), 20(6)]。- 向上调整(Shift Up):下标 6 的父节点下标为 ,对应元素是
10。20 > 10,交换位置 6 和位置 3!数组变成[25(1), 13(2), 20(3), 12(4), 9(5), 10(6)]。- 继续往上:位置 3 的父节点是 (即
25),20 < 25,调整停止。 结论:最终序列[25, 13, 20, 12, 9, 10]。
📦 五、真题扩展包(外部排序、败者树、置换-选择、最佳归并树)
1. 外部排序与败者树(Loser Tree)—— 考察频率:⭐⭐⭐
核心公式与考点
- 外部排序总时间 =
内部排序时间+外存信息读写(I/O)时间(主要瓶颈!) +内部归并比较时间。- 归并趟数:若有 个初始归并段,采用 路平衡归并,则归并趟数 。
- 读写磁盘总次数 =
初始生成归并段读写 2 次+每趟归并读写 2 次 × S 趟= 。- 败者树(Loser Tree)的作用:
- 当增大归并路数 以减少归并趟数 时,内存中每次从 个归并段选最小值的内部比较次数会增加(普通比较需 次)。
- 引入 路败者树 后,树高(不含最顶上的冠军结点)为 ,每次选出最小元素后的重构只需比较 次,使内部归并时间不再随 的增大而受影响!
2. 置换-选择排序(Replacement Selection)—— 考察频率:⭐⭐
一句话记忆
“利用最小堆生成突破内存容量限制的更长初始归并段,平均长度为 2w”( 为内存工作区大小)。
📝 小题自测(点击展开看手算)
题目:内存工作区容量 ,输入序列
[5, 2, 8, 1, 9, 3],用置换-选择排序生成初始归并段。手算步骤:
- 初始读入前 3 个元素:
[5, 2, 8]。- 选出最小元素
2输出(当前归并段末尾MINMAX = 2),读入下一个元素1。因为1 < 2,1被冻结(打标*1,属于下一段),当前有效元素[5, 8, *1]。- 选出有效最小元素
5输出(MINMAX = 5),读入9。因为9 > 5,9可参与当前段,工作区[8, 9, *1]。- 选出有效最小元素
8输出(MINMAX = 8),读入3。因为3 < 8,冻结为*3,工作区[9, *3, *1]。- 选出有效最小元素
9输出,工作区只剩冻结元素[*3, *1],第 1 个归并段结束:[2, 5, 8, 9]。- 解冻
[*3, *1],依次输出得 第 2 个归并段:[1, 3]。
3. 最佳归并树(K 叉哈夫曼树应用)—— 考察频率:⭐⭐⭐
核心心法(刻在脑子里)
- 本质定位:最佳归并树就是 叉哈夫曼树,目标是使整棵树的带权路径长度(WPL)最小,从而让外部排序读写外存的 I/O 次数最少。
- 虚段的本质:每进行一次 路归并,都会将 个归并段合成 1 个新段,结点数净减少 个。为保证每次归并都严格凑齐 个段(严格 叉树),若总段数不够,必须在最底层补入权值(长度)为 0 的虚段!
- 秒杀公式:若 :
- 若 :无需补虚段(补 0 个);
- 若 :需补充虚段个数 。
为什么要补“虚段”?底层推导与直觉记忆
- 数学推导: 设归并树有 个叶子(初始归并段),加上 个虚段,总叶子数为 。 设非叶结点(归并次数)为 个。在一棵严格 叉树中:
- 每个非叶结点度数均为 ,总分支数为 ;
- 总结点数 = 分支数 ,即 ;
- 整理得: 必须是 的整数倍!
- 物理意义: 如果段数凑不齐严格 叉,那么必须有一次归并参与的段数少于 。这“少段”的归并必须安排在第一趟(离根最远的最底层)!因为虚段长度为 0,让权值为 0 的虚段在最底层参与合并,能确保所有真实的、权值大的归并段尽可能靠近树根,使总 WPL 达到真正最优!
命题人考场陷阱:公式分母是 而不是 !
- 很多同学在考场上一紧张写成 或者 ,这是最致命的失分点!
- 避坑口诀:“分子分母都减 1,余数再被除数减”!
- 算余数:
- 算虚段:
408 必考公式:WPL 与 I/O 次数的关系!
- 最佳归并树的 WPL = 归并过程中的总读记录数 = 总写记录数。
- 外部排序归并阶段的总 I/O 次数(总读写次数) = !(千万别忘了乘以 2,因为一读一写是 2 次!)
📝 小题自测 1:虚段计算(【典型统考真题】点击展开看秒杀)
题目:设外存上有 120 个初始归并段,进行 12 路归并时,为实现最佳归并,需要补充的虚段个数是( )。
A. 1 B. 2 C. 3 D. 4手算步骤(考场 15 秒秒杀):
- 提取参数:初始归并段数 ,归并路数 。
- 代入口诀计算余数:
,余数 。- 计算所需补充的虚段数:
个。- 验算:补 2 个虚段后,总段数为 。 次归并,正好构成严格 12 叉哈夫曼树!
📝 小题自测 2:WPL 与读写 I/O 次数计算(点击展开看手算)
题目:有 5 个初始归并段,长度分别为
9, 30, 12, 18, 3(单位:块)。进行 3 路归并,求最佳归并树的 WPL 以及归并过程中的总读写块数(I/O 次数)。手算步骤:
- 判虚段:。
,余数为 0,无需补虚段。- 构造 3 叉哈夫曼树:
- 第一次合并最小 3 个:
3 + 9 + 12 = 24。- 第二次合并剩余 3 个:
18 + 24 + 30 = 72。- 计算 WPL: 。
- 总读写块数(I/O 次数):
次。