18.1 排序的基本概念·选择题讲评
多选：插入稳定、归并稳定、堆排序不稳定、快速排序通常不稳定？
考研计算机 408 全程课 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 章9第 2 章8第 3 章14第 4 章20第 5 章7第 6 章21第 7 章20第 8 章21第 9 章25第 10 章9第 11 章8第 12 章12第 13 章16第 14 章23第 15 章15第 16 章21第 17 章9第 18 章10第 19 章8第 20 章1第 21 章4第 22 章4第 23 章6第 24 章2第 25 章1第 26 章3第 27 章14第 28 章14第 29 章18第 30 章8第 31 章19第 32 章13第 33 章16第 34 章3第 35 章6第 36 章8第 37 章8第 38 章9第 39 章7第 40 章8第 41 章8第 42 章19第 43 章19第 44 章9第 45 章10第 46 章4第 47 章4第 48 章4第 49 章4第 50 章16第 51 章20第 52 章16第 53 章12第 54 章14第 55 章25第 56 章14第 57 章10第 58 章4第 59 章6
第 1 页 · 正面（题目）
28.2.1 插入排序
对[3,1,2]写每趟数组？
38.2.3 希尔排序
增量2时下标0,2,4属于一组。对[5,4,3,2,1]列出分组并排序。
48.2 插入排序、希尔排序·选择题讲评
哪个适合小规模近乎有序表？
58.2 插入排序、希尔排序·综合题讲评
解释折半插入比较次数下降但移动次数不变。
68.3.1 冒泡排序
[1,2,3]优化冒泡比较一趟后结束，交换0次。
78.3.2 快速排序
已排序数组总选首元素时递推T(n)=T(n-1)+O(n)，？
88.3 冒泡排序、快速排序·选择题讲评
多选：快排平均nlogn、最坏n²、通常原地、通常不稳定？
98.3 冒泡排序、快速排序·综合题讲评
全相等n项用二路与三路快排比较递归规模，三路一次结束。
108.4.2 堆排序、堆的插入删除
0基下标i的孩子是2i+1、2i+2。n=7最后非叶下标2。
第 1 页 · 背面（答案）
答案[1,3,2]、[1,2,3]。
答案全选。
答案直接插入排序。
需提交逐趟数组状态、复杂度和边界测试。
需提交逐趟数组状态、复杂度和边界测试。
需提交逐趟数组状态、复杂度和边界测试。
答案全选。
答案O(n²)。
需提交逐趟数组状态、复杂度和边界测试。
需提交逐趟数组状态、复杂度和边界测试。
第 2 页 · 正面（题目）
118.4 堆排序、堆的插入删除·选择题讲评
大根堆[9,7,8,1]删顶后末元素1补位，向下与8交换。
128.4 堆排序、堆的插入删除·综合题讲评
海量数据求前100大，时间O(nlog100)、空间O(100)。
138.5.1 归并排序
合并[2,5]与[1,3,6]，？
148.5.2 基数排序
为什么个位相同元素次序必须保留？
158.5.3 计数排序
键范围[-2,2]如何索引？
168.5 归并排序、基数排序·选择题讲评
小值域整数大量重复优先考虑什么？
178.5 归并排序、基数排序·综合题讲评
[4,3,2,1]逆序对数？
188.6 教材 8.6·选择题讲评
要求最坏nlogn且O(1)辅助空间，典型选择堆排序。
198.6 教材 8.6·综合题讲评
解释标准库排序为何常采用内省排序：快排快，深度过大转堆保最坏界，小段转插入。
208.7.1 外部排序
16段做4路需要几趟？
第 2 页 · 背面（答案）
需提交逐趟数组状态、复杂度和边界测试。
需提交逐趟数组状态、复杂度和边界测试。
答案高位处理依赖低位已有次序。
答案[1,2,3,5,6]。
答案计数排序。
答案整体加2映射到0..4。
需提交逐趟数组状态、复杂度和边界测试。
答案6，归并计数O(nlogn)。
答案2趟。
需提交逐趟数组状态、复杂度和边界测试。
第 3 页 · 正面（题目）
218.7.3 败者树
k=8时每输出一个元素需数量级多少次比较？
228.7.5 最佳归并树
段长1,2,4,8的2路最佳代价？
238.7 外部排序、败者树·选择题讲评
多路归并中败者树的主要作用？
248.7 外部排序、败者树·综合题讲评
说明增加内存如何减少I/O：能生成更长初始段、提高归并路数，从而减少归并趟数。
258.1 排序的基本概念
判断选择排序是否稳定并构造反例？
第 3 页 · 背面（答案）
答案25。
答案O(log8)=O(3)。
需提交逐趟数组状态、复杂度和边界测试。
答案把选最小头元素降到O(logk)比较。
答案通常不稳定，如(2,a),(2,b),(1)首轮交换会颠倒两个2。