3.3 查找与排序
本篇定位：查找与排序是数据结构与算法中真题密度最高的板块——9 年共 5 题直接命中（2019 单59、2023 单23、2024 单27/28/多81），全部落在"折半查找比较次数"与"排序每趟定位"两类计算/判定题。2027 预测同样点名：查找（折半/平均）、排序（冒泡/快排/堆排每趟定位）。本章把查找两大方法（顺序/折半）与八大排序的核心特性讲透，是第 3 篇的"得分主力"。 数据依据：
01-真题/真题文本/+01-真题/考点汇总/；答案以专业判断为准（2023 单23 常见答案与本书一致，逐题核对过）。 阅读提示：与 3.2 章二叉排序树、堆衔接；复杂度（O(log n)/O(n log n)）与 3.4 章算法分析衔接。
一、考点定位（本章真题统计）
| 考点 | 真题锚点 | 频次 | 考法 |
|---|---|---|---|
| 折半查找比较次数 | 2019 单59、2024 单28 | 2 年 | 98 个元素最多 7 次；8 元素不存在最多 4 次 |
| 排序每趟定位 | 2023 单23、2024 多81 | 2 年 | 简单选择/快排/堆排每趟至少确定 1 个最终位置（希尔/归并不保证） |
| 冒泡排序过程判定 | 2024 单27 | 1 年 | 给三趟结果判断所用排序算法 |
| 单链表顺序查找 | 2025 单49 | 1 年 | 平均比较 (N+1)/2 次（已在 3.1 章详解） |
命题规律：查找考"次数计算"（折半查找 ⌊log₂n⌋+1 次）、排序考"每趟定位"（哪些算法每趟至少确定一个最终位置）与"过程判定"（给中间结果反推算法）。2027 预测 1–2 题：折半查找次数、排序每趟定位、稳定性辨析。核心能力：背熟"每趟定位四兄弟"（冒泡/选择/快排/堆）+ 折半查找公式。
二、知识框架（先搭骨架）
查找
├── 顺序查找：从头到尾逐个比较
│ ├── 平均比较 (n+1)/2 次；时间 O(n)
│ └── 对存储结构无要求（顺序表/链表均可）
├── 折半查找（二分查找）：每次取中间元素比较，减半搜索区间
│ ├── 前提：顺序存储 + 有序（链表不行！）
│ ├── 最多比较 ⌈log₂(n+1)⌉ = ⌊log₂n⌋+1 次；时间 O(log n)
│ └── 2019 单59：98 元素 → 7 次；2024 单28：8 元素 → 4 次
├── 分块查找：块间有序 + 块内无序，索引表 + 顺序/折半
├── 哈希查找：散列函数 + 冲突处理（开放定址/链地址）
└── 二叉排序树查找：左小右大，平均 O(log n)
排序（八大，内部排序）
├── 插入类：直接插入 O(n²) 稳定、希尔 O(n^1.4~n²) 不稳定
├── 交换类：冒泡 O(n²) 稳定、快速 O(n log n) 不稳定（最坏 O(n²)）
├── 选择类：简单选择 O(n²) 不稳定、堆排序 O(n log n) 不稳定
├── 归并排序：O(n log n) 稳定
└── 基数排序：O(d(n+r)) 稳定（非比较排序）
核心判定（必背）：
├── 每趟至少确定 1 个最终位置：冒泡、简单选择、快排、堆（口诀：快速选择冒泡堆）
│ （希尔、归并、插入、基数不保证——口诀：希归插基）→ 2023 单23、2024 多81
├── 稳定排序：冒泡、直接插入、归并、基数（口诀：冒直基归）
└── 不稳定：选择、快排、堆、希尔（口诀：选快希堆）
一句话记忆：查找两兄弟——顺序 (n+1)/2、折半 ⌊log₂n⌋+1（要求顺序存储+有序）；排序每趟定位四兄弟「快速选择冒泡堆」——快速/简单选择/冒泡/堆（不保证的是「希归插基」：希尔/归并/直接插入/基数）；稳定四兄弟「冒直基归」——"喝酒了，不要直接回家，稳当安全些"；不稳定四兄弟「选快希堆」——"我们选择快些堆，但地基不稳，房子塌了"。
三、考点详解
3.1 顺序查找
精确定义：顺序查找 = 从表的一端开始，逐个将关键字与给定值比较，找到则查找成功。
平均比较次数：每个位置等概率时，第 i 个位置比较 i 次 → 平均 (1+2+…+n)/n = (n+1)/2 次。时间复杂度 O(n)。
适用条件：对存储结构无要求（顺序表、链表都行），对是否有序无要求——这是与折半查找的本质区别。
3.2 折半查找（二分查找）（2019 单59、2024 单28，必考计算）
精确定义：折半查找 = 每次取有序序列的中间元素与给定值比较，相等则成功；给定值小则在前半部分继续、大则在后半部分继续，每比较一次搜索区间减半。
两个前提（缺一不可）：
- 顺序存储（数组，可随机存取）——链表不行（无法取中间元素）；
- 按关键字有序（递增或递减）。
比较次数（成功最坏与失败最多是同一个上限）：
- 最多比较次数 = 判定树深度 = ⌈log₂(n+1)⌉ = ⌊log₂n⌋ + 1（两个写法恒相等——它们各锚同一个区间 [2^(k−1), 2^k − 1] 的一端：⌊log₂n⌋ 认左端 2^(k−1)、⌈log₂(n+1)⌉ 认右端 2^k − 1。边界自检：n=15 → ⌈log₂16⌉=4、⌊log₂15⌋+1=4，吻合——天花板对恰好整数不抬升（⌈4⌉=4）；n=16 → 两式同给 5。把折半过程画成二叉判定树：第 1 次比较在根、第 2 次在第 2 层……最多比到第几层，就是最多几次）；
- 考场 30 秒法（2 的幂夹 n）：看 n 落在哪个区间 [2^(k−1), 2^k − 1]，最多就比较 k 次。98 ∈ [64, 127] → 7；8 ∈ [8, 15] → 4；
- 2019 单59：98 个元素 → 7 次（选 D；真题题干作"二分法查找"，与折半同义）；
- 2024 单28：长度 8 的顺序表查找不存在的元素 → 4 次（选 B）。
2024 单28 的坑（"不存在的元素"怎么数）：查找失败 = 一路比到区间为空才死心，比较次数 = 判定树上一条路径走过的节点数，上限就是判定树深度——所以失败最多次数 = 成功最坏次数 = ⌈log₂(n+1)⌉，失败不会"多查一轮"。8 个元素：判定树深度 ⌈log₂9⌉ = 4 → 成功最坏 4 次、失败最多 4 次（选 B）。坑：以为"查不到就得扫完全表"或"失败要额外加一次"而错选 5/6。
推导验证（2019 单59）：98 个元素，比较过程区间长度变化：98→49→24→12→6→3→1→0，共 7 次（最后一次比较后区间为空，判定不存在）。这与真题解析一致（每次查找缩小一半：49、24、12、6、3、1、0 → 7 次）。
3.3 排序算法全家福（核心：每趟定位 + 稳定性 + 复杂度）
八大排序三张表（必背）：
表 1：每趟定位（2023 单23、2024 多81 直接考）
| 算法 | 每趟至少确定 1 个最终位置？ | 原因 |
|---|---|---|
| 冒泡排序 | ✅ | 每趟把最大（或最小）元素冒泡到位 |
| 简单选择排序 | ✅ | 每趟选出最小（或最大）放入最终位置 |
| 快速排序 | ✅ | 每趟把基准元素放到最终位置 |
| 堆排序 | ✅ | 每趟堆顶元素（最大/最小）输出到最终位置 |
| 希尔排序 | ❌ | 按步长分组局部排序，不保证定位 |
| 二路归并排序 | ❌ | 得到若干局部有序段，不保证定位 |
| 直接插入排序 | ❌ | 每趟只保证前 i 个有序，不保证最终位置 |
| 基数排序 | ❌ | 每趟按位分配再收集，不保证任何元素到最终位置 |
口诀：每趟定位四兄弟「快速选择冒泡堆」（快速／简单选择／冒泡／堆）——读法："快速选择，冒泡堆"（快速点选 → 冒个泡 → 堆成堆）。
- 反面记更省事：不保证定位的是「希归插基」（希尔／归并／直接插入／基数）——8 个排序刚好 4 + 4 分完。
- ⚠️ 这四兄弟里只有冒泡是稳定的（选择、快排、堆都不稳定）⇒「每趟定位」与「稳定」两个集合只共享冒泡。
2023 单23（单选）：I 简单排序、III 快速排序、IV 堆排序 → 选 B（仅 I、III、IV）；II 希尔、V 二路归并不保证。 2024 多81（多选）：A 简单选择、C 快速、D 堆排序 → 选 ACD；B 希尔不保证。两题考点完全一致——跨年重复题（总纲附录 C 记录 12 对跨年重复题之一）。
表 2：稳定性（防漏网重点）
| 稳定 | 不稳定 |
|---|---|
| 冒泡、直接插入、归并、基数 | 简单选择、快排、堆、希尔 |
口诀（故事式，只留这一套）
- 稳定四兄弟「冒直基归」——"喝酒了，不要直接回家，稳当安全些"；不稳定四兄弟「选快希堆」——"我们选择快些堆，但地基不稳，房子塌了"。
- 字面拆解：冒泡、直接插入、基数、归并 ／ 选择、快速、希尔、堆。
为什么这几个稳定、那几个不稳定（记住原理就不用背表）
- 只跟"邻居"换的 → 稳定：冒泡（相邻交换）；直接插入（逐个后移，只在严格大于时才动）；归并（合并时相等取左边）；基数（按位分配再收集，原有次序不变）。
- 会"隔空换位"的 → 不稳定：简单选择（把远处的最小值换到前面，可能越过相等元素）；快速（划分时首尾远距离交换）；希尔（按步长分组、跨组跳跃）；堆（调整时堆顶与末尾远端交换）。
- 一句话："隔空换位"必不稳，"挨个挪位"必稳定；归并、基数是"另开空间按序搬"，所以也稳定。
⚠️ 两个"四兄弟"别串台（本卷最容易混的一处） · 每趟定位四兄弟 ＝ 冒泡／简单选择／快速／堆（每趟至少定死一个元素的最终位置）； · 稳定四兄弟 ＝ 冒泡／直接插入／归并／基数。 两者只共享"冒泡"一个，其余三个完全不同。问"哪些算法每趟能确定最终位置"时写成"冒泡/插入/归并/基数"，就是典型失分。
表 3：时间复杂度
| 算法 | 平均 | 最坏 | 空间 |
|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) |
| 简单选择 | O(n²) | O(n²) | O(1) |
| 直接插入 | O(n²) | O(n²) | O(1) |
| 希尔 | O(n^1.4) | O(n²) | O(1) |
| 快速 | O(n log n) | O(n²)（已有序时退化） | O(log n)（递归栈） |
| 堆 | O(n log n) | O(n log n) | O(1) |
| 归并 | O(n log n) | O(n log n) | O(n) |
| 基数 | O(d(n+r)) | O(d(n+r)) | O(n+r) |
复杂度口诀（故事式）
- O(n²) 三兄弟「冒简直」——"啊么么（冒），简直了"：冒泡、简单选择、直接插入。
- O(n log n) 三兄弟「快堆归」——"你龟儿，给老子堆快得"：快速、堆、归并。
- 例外别混进去：希尔（O(n^1.4)~O(n²)，不属任何一组）、基数（O(d(n+r))，非比较排序）。
记忆要点：快排平均最快但最坏 O(n²)（原序列已有序且基准取首元素时）；归并稳定且最坏也是 O(n log n)，代价是 O(n) 辅助空间；希尔最坏 O(n²) 但平均比插入快。
3.4 冒泡排序过程判定（2024 单27）
精确定义：冒泡排序 = 重复扫描序列，相邻元素两两比较，顺序错误则交换；每一趟把当前未排序区间的最大（或最小）元素"冒泡"到一端。
2024 单27 真题：对（2,15,16,90,5,10）排序，前三趟结果：
- 第 1 趟：2,15,16,5,10,90（90 冒泡到最后）
- 第 2 趟：2,15,5,10,16,90（16 到位）
- 第 3 趟：2,5,10,15,16,90（15 到位）
- 已有序：2,5,10,15,16,90
判定：每趟把当前最大元素推到末尾、相邻交换 → 冒泡排序（选 A）。干扰项：希尔（按步长分组，中间态不会这样整齐）、归并（成段有序）、基数（按位分配）。
判定口诀：看"每趟是否把最大/最小推到一端 + 相邻元素交换"→ 冒泡；"每趟选最小放入前部"→ 简单选择；"基准两侧划分"→ 快排。
四、易错坑汇总（命题人惯用陷阱）
- 折半查找的两个前提：顺序存储 + 有序——链表不能折半（无法取中间元素）；无序不能折半。常设"单链表也可以折半"陷阱。
- 折半查找次数：98 元素 7 次（2019 单59）；8 元素失败查找 4 次（2024 单28）。公式 ⌈log₂(n+1)⌉；注意"查找不存在元素"= 失败查找，次数按判定树深度算。
- "希尔排序每趟确定最终位置"是错误说法（2023 单23、2024 多81 反复考）——希尔按步长分组局部排序，不保证；归并同样不保证。每趟定位四兄弟：冒泡/选择/快排/堆。
- 快排最坏 O(n²)——原序列已有序且基准取首（或尾）元素时，每次划分极不平衡 → 退化为 O(n²)。"快排最坏 O(n log n)"是错误说法。
- 稳定性：快排不稳定（交换可能越过相等元素）、选择不稳定（交换破坏相对次序）——"快排是稳定排序"是错误说法。稳定四兄弟：冒直基归（"喝酒了，不要直接回家，稳当安全些"）。
- 归并的空间 O(n)——"归并排序空间复杂度 O(1)"是错误说法（需要辅助数组）。
- 冒泡过程判定（2024 单27）——给三趟结果选算法，看"每趟最大推到末尾 + 相邻交换"；别被"希尔"干扰（希尔中间态是分组有序，不是这种整齐的尾部定型）。
- 顺序查找对链表可用、折半对链表不可用——顺序查找无结构要求；折半必须顺序存储。
五、横向扩展（防漏网：本章边界内、真题尚未考但可能补考的点）
说明：横向扩展覆盖"大纲范围内但 9 年真题未考过"的知识，标注【新增概率】供取舍。
- 排序稳定性判定【高】：给具体算法问是否稳定（冒直基归稳定，选快希堆不稳定）——2023/2024 考过"每趟定位"，稳定性是同一知识族的高概率补考点。
- 各排序时间复杂度匹配【高】：O(n²) 三兄弟、O(n log n) 三兄弟——概念匹配题。
- 堆排序的底层（完全二叉树）【中】：大根堆（堆顶最大）/小根堆；建堆、堆顶输出后调整——与 3.2 章完全二叉树编号衔接。
- 哈希查找与冲突处理【中】：散列函数（除留余数法）、冲突处理（开放定址法/链地址法）——"哈希表查找时间复杂度近似 O(1)"概念题。
- 分块查找【低】：块间有序、块内无序；索引表查找 + 块内顺序查找——"索引"概念与数据库索引衔接（第 4 篇）。
- 二叉排序树查找【中】：平均 O(log n)、最坏 O(n)（退化链）——与 3.2 章衔接。
- 外部排序【低】：多路归并，用于数据量超内存——"外部排序基础是归并"判断题。
- 折半查找判定树【低】：把折半过程画成二叉树（判定树）——"折半查找成功/失败比较次数=判定树深度"。
六、真题演练（代表性真题 + 解析）
例 1（2019 单59） 设有 98 个已排序元素，采用二分法查找时，最大比较次数是（口径已核）。 A. 49 B. 15 C. 20 D. 7
答案：D。折半查找每比较一次区间减半：98→49→24→12→6→3→1→0，共 7 次（⌈log₂(98+1)⌉ = ⌈log₂99⌉ = 7，因 2^6=64 < 99 ≤ 128=2^7）。干扰项 A（49）：第一次比较后剩余的元素数——把"砍完剩多少"当"比较了几次"。口诀：折半次数看 ⌈log₂(n+1)⌉。 ⚠️ 文本勘误：真题原选项为 A.49 / B.15 / C.20 / D.7（选 D）；旧版误排"A.5 B.6 C.7 D.8、选 C"（自编选项），已按真题原文恢复。
例 2（2024 单28） 已知一个长度为 8 的顺序表 L，其中的元素按关键字有序排列。若采用折半查找法查找一个不存在的元素，则关键字比较次数最多是（口径已核）。 A. 3 B. 4 C. 5 D. 6
答案：B。失败查找最多比较 ⌈log₂(8+1)⌉ = ⌈log₂9⌉ = 4 次（判定树深度 4：比较到叶子仍不等 → 区间空 → 判定不存在）。口诀：失败查找次数=判定树深度=⌈log₂(n+1)⌉。
例 3（2024 单27） 对一组数据（2，15，16，90，5，10）进行排序，若前三趟排序结果如下： （1）2，15，16，5，10，90 （2）2，15，5，10，16，90 （3）2，5，10，15，16，90 则采用的排序算法最可能是（口径已核）。 A. 冒泡排序 B. 希尔排序 C. 归并排序 D. 基数排序
答案：A。每趟把当前最大元素冒泡到末尾（90→16→15），且是相邻两两比较交换——典型冒泡排序。希尔按步长分组（中间态不是这种尾部定型）；归并成段有序（不会每趟只定一个尾部）；基数是按位分配。判定口诀：每趟最大推到尾部 + 相邻交换 = 冒泡。
例 4（2023 单23） 下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（口径已核）。 I. 简单排序 II. 希尔排序 III. 快速排序 IV. 堆排序 V. 二路归并排序 A. 仅 I、II、IV B. 仅 I、III、IV C. 仅 I、IV、V D. 仅 II、III、IV
答案：B。**简单选择（I）**每趟选最小放入最终位置；**快速（III）**每趟把基准放到位；**堆排序（IV）**每趟堆顶输出到位。**希尔（II）**按步长局部排序、**归并（V）**成段有序——都不保证。口诀：每趟定位=冒泡、选择、快排、堆；希尔归并不行。
例 5（2024 多81） 以下排序方法中，每一趟排序至少能确定 1 个元素最终位置的有（口径已核）。 A. 简单选择排序 B. 希尔排序 C. 快速排序 D. 堆排序
答案：ACD。与 2023 单23 同一考点（跨年重复题）：简单选择、快速、堆排序每趟至少确定 1 个最终位置；希尔排序不保证。口诀：选快堆=每趟定位；希尔=不保证。
例 6（防漏网·稳定性） 下列排序算法中，属于稳定排序的是（口径已核）。 A. 快速排序 B. 简单选择排序 C. 直接插入排序 D. 堆排序
答案：C。稳定四兄弟：冒泡、直接插入、归并、基数；快速（交换破坏次序）、选择（交换破坏次序）、堆（堆顶交换）、希尔（跨步长交换）均不稳定。口诀：稳定「冒直基归」、不稳定「选快希堆」。
七、本章小结
- 一条主线：查找（顺序 (n+1)/2 → 折半 log₂n+1 要求顺序存储+有序）→ 八大排序三张表（每趟定位四兄弟 / 稳定性四兄弟 / 复杂度三档）。
- 必背计算：折半查找最多 ⌈log₂(n+1)⌉ 次（98 元素→7 次、8 元素失败→4 次）；顺序查找平均 (n+1)/2。
- 必背判定：每趟至少确定 1 个最终位置 = 快速选择冒泡堆（快速/简单选择/冒泡/堆；不保证＝希归插基）；稳定 = 冒直基归；不稳定 = 选快希堆。
- 必背复杂度：O(n²)「冒简直」（啊么么（冒），简直了）；O(n log n)「快堆归」（你龟儿，给老子堆快得）；快排最坏 O(n²)；归并空间 O(n)。
- 衔接预告：堆/二叉排序树→3.2 章；复杂度分析→3.4 章；哈希/索引→第 4 篇数据库（索引原理）。