编程珠玑
问题求解思维

01位图排序：空间换洗牌

论域是有界整数、关键字互不重复时，可以用「值即下标」的位向量代替比较排序。

扫一遍输入，把出现过的值在位图里置 1；再按论域从小到大扫位图，为 1 的依次输出。时间 Θ(n+U)（n 为输入长度，U 为论域大小），空间 Θ(U) bit，不是 n 个整型指针。只记录存在性：键须是有界整数且互异（或只关心出现与否）。缺这些约束，位图不能当通用排序。

02写对二分为什么难

折半查找的前提：有序的顺序表。链表没有随机 O(1)，不能当这份教案里的二分容器。循环要钉死不变式：答案若存在，永远落在当前闭区间里。非负索引闭区间常用 mid = lo + (hi - lo)/2，避免 (lo+hi)/2 相加溢出。停机条件与「找到 / 插入位置」不要混成一个返回值还不声明。

最好成功匹配可以第一次中点就命中，Θ(1)；最坏 Θ(log n)。不要和朴素串匹配的最好成功匹配 Θ(m) 混用。

03采样与估算

工程上常见：流式数据里均匀抽 k 个、用抽样估计数。本课能留下的句子只有「平均复杂度必须声明分布或随机化假设」——和快排平均 O(n log n) 要带随机输入/随机枢轴是同一纪律。

04性能锦囊（概览）

先保证对，再问热路径。渐进界管增长，常数与局部性管这一次运行。不要用「珠玑里某次加速多少倍」当 408 数字；本站不编具体加速比。

结构选择仍回全书：顺序表按下标 O(1)、按位置插入 O(n)；单链表定位 O(n)，改链要前驱。建堆 O(n)，堆排序最坏 O(n log n)，通常不稳。

章末自测