数据结构收官篇讲查找与排序。这块每年 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(nr))O(d(nr))—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~51.使用二分查找的前提是 。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. 115.冒泡排序在最好情况下序列已有序的时间复杂度是 。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 各从哪头开始长、拓扑排序怎么排。至此上午题知识版图全部点亮。