【软考备考】查找与排序详解：二分查找的前提、排序复杂度与稳定性（附 10 道练习）
数据结构收官篇，讲查找与排序。这块每年 2~3 分，考点收敛得惊人：
二分查找：前提条件 + 最多比较次数（一句话考点）；
八大排序：时间复杂度对比表（背下来就是分）；
稳定性：哪些排序稳定（千年考点，一个口诀解决）。
一、二分查找：两个前提，缺一不可
二分查找（折半查找）每次取中间元素比较，把查找范围砍掉一半，效率 O(log n)。但它的前提是两个条件同时满足：
① 顺序存储（数组）+ ② 元素有序
为什么缺一不可？有序才能"砍一半"（比中间值小就只看左半）；顺序存储才能 O(1) 取到中间元素——链表做不到随机访问，取个中间元素得从头爬，砍半的优势荡然无存。所以"链表上二分查找"是个伪命题，选项里出现就是错的。
最多比较次数：n 个元素的有序表，最坏情况下比较⌊log₂n⌋ + 1次。1024 个元素 → 10 + 1 =11 次。
二、八大排序：一张表背完
| 排序 | 类别 | 平均 | 最坏 | 最好 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 交换 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 直接插入 | 插入 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 简单选择 | 选择 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 希尔排序 | 插入 | O(n^1.3) | O(n²) | — | O(1) | 不稳定 |
| 快速排序 | 交换 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 堆排序 | 选择 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 基数排序 | 分配 | O(d(n+r)) | O(d(n+r)) | — | O(r) | 稳定 |
记忆规律：
O(n²) 三兄弟：冒泡、直接插入、简单选择（思路最朴素的三个）；
O(n log n) 三剑客：快排、堆排、归并；
两个"反常"要单记：快排最坏退化成 O(n²)；堆排序最坏也是O(n log n)，且空间 O(1)。
三、两个反直觉的点（坑所在）
反直觉一：基本有序对快排是最坏情况。快排选基准划分，若基准总是最大或最小（序列已基本有序时选端点基准就会这样），划分极不均衡，一侧空一侧满，递归退化成了单链 → O(n²)。而基本有序恰恰是插入/冒泡的高光时刻——直接插入排序此时接近 O(n)：每个元素几乎不用挪动。
反直觉二：快排"最快"，堆排"最稳"（性能上的稳）。平均意义下快排是内部排序的王者（常数小、缓存友好）；但它有 O(n²) 的软肋。要最坏情况也保证 O(n log n) 且空间 O(1)，选堆排序；要 O(n log n) 且稳定，选归并（代价是 O(n) 辅助空间）。
四、稳定性：一个口诀解决
稳定的定义：相等元素在排序后保持原来的相对次序。
口诀："快希选堆"不稳定——快排、希尔、简单选择、堆排序，这四个不稳定；其余（冒泡、直接插入、归并、基数）都稳定。
为什么不稳定？共性原因：存在跨距离的元素交换。快排的划分、堆的跨级调整、简单选择"选最小换到最前"、希尔的分组插入，都会让相等元素被"跳换"打乱次序；而冒泡、插入只做相邻交换，归并合并时先取左，天生保序。
场景选择题套路（软考爱考）：
基本有序 → 直接插入 / 冒泡；
平均最快 → 快排；
最坏也要 O(n log n) + 省空间 → 堆排序；
要稳定 → 归并排序。
五、10 道练习题
基础题（1~5）
1.使用二分查找的前提是（ ）。
A. 链式存储且元素有序 B. 只需元素有序 C. 顺序存储且元素有序 D. 只需顺序存储
2.快速排序的平均时间复杂度是（ ）。
A. O(n) B. O(n log n) C. O(n²) D. O(log n)
3.下列排序算法中，属于稳定排序的是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 简单选择排序
4.对含 1024 个元素的有序顺序表进行二分查找，最多需要比较（ ）次。
A. 10 B. 512 C. 1024 D. 11
5.冒泡排序在最好情况下（序列已有序）的时间复杂度是（ ）。
A. O(n) B. O(n²) C. O(n log n) D. O(1)
进阶题（6~10，带坑）
6.下列排序算法中，全部属于不稳定的一组是（ ）。
A. 快速排序、堆排序、简单选择排序 B. 冒泡排序、归并排序、基数排序 C. 直接插入排序、冒泡排序、归并排序 D. 堆排序、归并排序、快速排序
7.快速排序在最坏情况下（如序列已基本有序）的时间复杂度是（ ）。
A. O(n log n) B. O(n²) C. O(n) D. O(log n)
8.堆排序在最坏情况下的时间复杂度是（ ）。
A. O(n²) B. O(n) C. O(n log n)，且需 O(n) 辅助空间 D. O(n log n)
9.待排序的数据量很大且基本有序，最合适的排序算法是（ ）。
A. 快速排序 B. 直接插入排序 C. 堆排序 D. 简单选择排序
10.排序算法的"稳定性"是指（ ）。
A. 算法运行时间稳定不变 B. 任何输入下时间复杂度不变 C. 相等元素在排序后保持原来的相对次序 D. 不需要辅助存储空间
六、答案与详解
1. C顺序存储 + 有序，缺一不可。选 B 的漏了存储结构——链表上元素再有序也没法 O(1) 取中间点，二分无从谈起。
2. B快排平均O(n log n)，是平均最快的内部排序。
3. C默口诀"快希选堆不稳定"：四个选项里快排、堆、简单选择全在口诀里，只有归并稳定。
4. D⌊log₂1024⌋ + 1 = 10 + 1 =11 次。选 A 的是忘了"+1"——二分砍到只剩 1 个元素时还要比较一次才确定。
5. A冒泡最好情况：一趟扫描发现没有交换，直接收工 →O(n)。
6. A"快希选堆"全员集合：快排、堆、简单选择，正是不稳定四人组（差个希尔）。B、C 里全是稳定派，D 里混进了归并。
7. B大坑：基本有序是快排的最坏情况——基准划分极度不均，退化成 O(n²)。同一个"基本有序"，对插入排序是天堂（O(n)），对快排是地狱，软考就爱在这个反差上下手。
8. D堆排序最坏情况也是 O(n log n)，且辅助空间 O(1)——这是它比快排"稳"的地方（性能的稳）。选 C 的把归并的空间复杂度（O(n)）安到了堆排头上。
9. B数据基本有序→ 直接插入排序接近 O(n)，是最优选择。选 A（快排）的正好踩进第 7 题的坑：基本有序让快排退化成 O(n²)，是最差选择之一。场景题先把"输入特点"圈出来。
10. C稳定性只讨论一件事：相等元素的相对次序是否保持。和运行时间（A）、复杂度（B）、辅助空间（D）统统无关。
七、五句话带走
二分查找前提：顺序存储 + 有序；最多比较⌊log₂n⌋+1次；
复杂度家族：O(n²) 三兄弟（冒泡、插入、选择），O(n log n) 三剑客（快、堆、归并）；
两个反常：快排最坏 O(n²)（基本有序时），堆排最坏也 n log n 且 O(1) 空间；
稳定性口诀："快希选堆"不稳定，其余稳定；定义就一句——相等元素相对次序不变；
场景题：基本有序选插入，平均最快选快排，最坏保证选堆排，要稳定选归并。
下一篇预告：数据结构的最后一块拼图——图：邻接矩阵和邻接表各适合什么图、DFS 和 BFS 的本质区别（一个用栈一个用队列）、最小生成树的 Prim 和 Kruskal 各从哪头开始长、拓扑排序怎么排。至此，上午题知识版图全部点亮。