1. 先从生活场景说起插入排序是怎么把一副乱牌理好的1.1 过程回顾一张一张抽出来往前插到正确位置我最早学插入排序的时候第一反应是这算法看起来一点也不“算法”不就是打牌的时候整理手牌吗后来才发现这种直觉恰恰是理解它最好的入口。想象你左手握着一把已经按从小到大排好的牌右手从桌上一次只能抽一张新牌。抽到新牌后你会从右往左一张一张跟左手的牌比找到第一个比这张牌小的位置把牌插进去。如果比到最左边都没找到更小的就放在最开头。整个过程里左手的牌始终是有序的只是牌数在增加。对应到数组上就是《算法导论》2.1节那段经典伪代码做的事情INSERTION-SORT(A) 1 for j 2 to A.length 2 key A[j] 3 // 把 A[j] 插入到已经有序的 A[1..j-1] 中 4 i j - 1 5 while i 0 and A[i] key 6 A[i1] A[i] 7 i i - 1 8 A[i1] key每次外层循环取一个“新牌”key也就是当前要处理的元素。然后用一个while循环从已排序区间的右侧往左侧扫描凡是比key大的元素都往后挪一位给key腾位置。最后把key放到该放的地方。数组下标从1开始的约定是很多教材统一采用的写法实际写代码时要习惯改成从0开始不过分析的逻辑完全一致。这里我多说一句初学的人常把“交换两个元素”和“插入”混在一起。插入排序不是交换而是“平移腾位”。后面的while循环让A[i1]A[i]本质是把一批元素整体向右移动最后key落位。这个细节在后面分析运行时间时非常重要因为它决定了移动次数和比较次数的计算方式。1.2 为什么叫“插入”排序增量法这个思路的力量插入排序属于“增量方法”的典型代表。所谓增量就是每轮处理一个元素把已处理的区域扩大一格扩大过程中保持区域有序。它不像归并排序那样把问题对半切开再合并也不像快速排序那样按枢纽元素做划分它就是一个朴素而直接的思路维护有序前缀逐步吞并无序后缀。这个思路的力量在于它把“排序”这个看似复杂的任务拆成了“在有序序列中找位置”和“腾出空位”两个极小的子问题。而这两个子问题又都建立在同一个递推关系上如果A[1..j-1]已经有序那么把A[j]插进去后A[1..j]也必然有序。于是问题规模n被转化成了n-1次同样的操作。这一递归视角虽然插入排序本身是迭代写法但它为后续学习归并排序、二分查找插入等进阶内容打下了很好的直觉基础。我还想强调一个容易忽略的点这个算法是“原地排序”的除了key这个临时变量不需要额外的等长数组。这一点在现代缓存友好的场景里很有意义也是它在小规模数据上能比某些高级排序更快的物理原因。后面我会专门讲工程里的应用这里先记住结论插入排序的常数因子很小虽然增长量级是n²但在n很小时往往表现出乎意料地好。2. 分析的起点把伪代码拆成能数得清的基本操作2.1 RAM模型先约定每条指令的成本《算法导论》第2.2节的核心不是教你写插入排序而是教你“怎么分析一个已经写好的算法”。它提出了一个非常实用的抽象模型随机访问机模型。在这个模型中一条普通指令比如赋值、比较、加法、数组下标访问都消耗一个单位的常数时间。至于这条指令具体是1纳秒还是2纳秒不影响渐近分析的结果。为什么要这样约定因为如果不做抽象你会陷入“数组访问和整数加法哪个更快”的细节里去。分析方法的目的不是精确到微秒而是搞清楚运行时间随输入规模n增长的趋势。RAM模型就好像物理里的“质点”假设把所有不必要的复杂都剥离掉只留下最本质的东西每条语句的执行次数。我在实际工程里很少真的用RAM模型去逐条数指令但这个模型的价值在于培养一种本能看到一段循环嵌套能立刻判断它的复杂度大概是几层n在相乘。这种本能是靠手推过一遍插入排序才长出来的。2.2 成本表与T(n)表达式这步是后面所有讨论的地基假设每条语句的执行代价是c_i再来统计每条语句被执行多少次。这里用到一个记号t_j表示外层循环第j次执行时内层while循环体实际执行的次数。注意t_j不固定它取决于输入数据。我把次数统计表重新梳理一遍这是后面所有推导的起点行代价执行次数for循环初始化及总判断c1nkey A[j] 以及外层递增、判断c2n-1插入注释与i初始化c4n-1while判断 A[i] keyc5Σ(t_j)j从2到nA[i1] A[i]c6Σ(t_j - 1)i i - 1c7Σ(t_j - 1)A[i1] keyc8n-1于是总的运行时间可以写成T(n) c1·n c2·(n-1) c4·(n-1) c5·Σ(t_j) c6·Σ(t_j-1) c7·Σ(t_j-1) c8·(n-1)这个式子看起来有点吓人但它其实只是在说总时间等于每条语句代价乘执行次数的累加。只要把Σ(t_j)在具体输入下的取值搞明白整个T(n)就清楚了。这也是为什么后面要分最好情况、最坏情况和平均情况来讨论因为t_j完全由输入决定。很多初学者会问为什么要抠到每一条语句这么细直接数循环层数不行吗对于插入排序当然可以但2.2节这么做的目的是示范一种通用方法当算法比较复杂、循环不规整时只有逐语句统计次数才是可靠的。我自己的体会是这个方法在分析二分插入排序、Shell排序的某些变体时尤其有用因为它们的内层循环次数不是简单的等差数列。3. 最好情况、最坏情况和平均情况差别到底在哪里3.1 最好情况输入已经有序时T(n)变成线性如果输入数组本来就是从小到大排好的会发生什么每轮外层循环取key时while循环里的条件是A[i] key也就是A[j-1] A[j]这个条件在有序数组里永远不成立。于是每个j对应的t_j都等于1内层循环体一次都不执行只做一次判断就退出。把t_j1代入前面的总和公式T(n) c1·n (c2c4c5c8)·(n-1)整理后得到T(n) (c1c2c4c5c8)·n - (c2c4c5c8)这是n的一次函数也就是线性时间。换句话说最好情况下插入排序只需要把数组从头到尾扫一遍比较并确认每个元素已经到位工作量跟数据规模成正比。这个结论对实际选择算法有直接影响。对一个几乎已经排好序的列表插入排序可能是最快的原地排序之一因为它几乎不做移动每次while判断一两次就结束。这个特性在工程上非常有价值比如某些缓存系统里维护增量更新后的有序列表。3.2 最坏情况逆序输入时求和公式如何展开反过来如果输入是严格递减的也就是每个新取出来的key都比当前有序区间里的所有元素小那么它必须一直比到区间最开头才能落位。这时第j轮内层循环要执行j-1次也就是t_j j。还需要注意while循环是两次判断i0和A[i]key。为了把key放在第一个位置循环体会执行j-1次而最后一次判断是在i0时因为不满足i0而退出所以判断次数是j次。于是Σ(t_j) Σ(j)j从2到n n(n1)/2 - 1Σ(t_j-1) Σ(j-1)j从2到n n(n-1)/2代入T(n)后最高次项是n²项系数为c5/2 c6/2 c7/2。于是T(n) (c5/2 c6/2 c7/2)·n² 低次项这就是二次时间。前面的分析说明同一个算法最好和最坏的差距可以非常大一个是n一个是n²。当n10000时最坏情况的时间大约是最好的10000倍。这个数量级上的差距就是渐近分析要抓住的重点。3.3 平均情况的直觉约一半的元素要移动如果把所有输入排列等概率地考虑那么内层while每轮大约有一半的元素需要移动。更精确地说对于第j轮key在前j个位置中落位的概率大致均匀因此平均要比较大约j/2次。把 j/2 从2加到n得到平均情况依然是n²量级只是系数比最坏情况小一半左右。这里最重要的是理解“平均情况并不是最好和最坏的几何平均而是概率意义上的期望”。在做算法选型时我们通常关心三类情况最坏情况的保证、平均情况的期望、以及特定应用里的输入分布。插入排序的三种情况都是多项式级别的区别只在系数和低阶项。正是这个“三种情况”的分析框架在后面学习快速排序的随机化版本、哈希表的装填因子时会反复出现。我在面试或评审代码时常听人说“插入排序是O(n²)所以不能用”。这个说法太粗了。如果输入规模只有几十或者数据接近有序插入排序的常数优势极可能胜过O(n log n)但常数较大的算法。后面第6节我会用一个贴近工程的例子说明这一点这里先记住渐近复杂度描述的是增长趋势不是绝对快慢。4. 循环不变式走一遍为什么能证明插入排序是对的4.1 初始化、保持、终止证明算法的三块拼图《算法导论》2.1节已经引入了循环不变式的概念2.2节的习题和过程分析里还会反复用到。循环不变式就是一条在循环每一次迭代之前都必须为真的性质。用它证明算法正确性需要三步初始化循环第一次迭代开始前不变式为真。保持如果某次迭代开始前为真那么下一次迭代开始前仍然为真。终止循环终止后不变式能帮助我们证明算法的结果是对的。这个套路看起来有点数学归纳法的味道但二者有区别。归纳法通常证明到无穷循环不变式却要利用终止条件收尾。也就是说“终止”这一环不是可有可无它保证了循环结束后我们拿到的状态正好是答案。对于插入排序我定义的不变式是在每一轮外层循环开始前子数组A[1..j-1]包含原来数组A[1..j-1]里的所有元素并且已经按非递减顺序排列。注意这里说的是“原来的元素”因为算法会原地移动元素如果不加这个限定性质就不完整。4.2 拿具体数组过一遍A[1..j-1]始终有序我用一个简单的数组来演示比如A [5, 2, 4, 6, 1, 3]下标从1开始。j2时key2有序前缀是[5]。内层把5往后移2放到索引1数组变成[2, 5, 4, 6, 1, 3]。迭代结束时A[1..2][2,5]是有序的。j3时key4。前缀是[2,5]。从5开始比较5比4大右移2不比4大停。把4放在索引2数组变成[2,4,5,6,1,3]。迭代结束时A[1..3][2,4,5]有序。j4时key66比前缀里最大的5还大while一次都不执行直接放在原位A[1..4]依然有序。这一步会让人产生“前面的工作白费了”的错觉但它恰恰说明最好情况为什么是线性的。j5时key1它比前缀所有元素都小。while一直跑到i0才停把5、6、4、2全部右移1放到索引1数组变成[1,2,4,5,6,3]。前缀A[1..5]有序。j6时key3经历类似的过程后停在索引3。最终数组变成[1,2,3,4,5,6]。每一轮循环结束后A[1..j]有序这个性质都成立。到j7时for循环的判断条件不满足循环终止。此时不变式告诉我们A[1..n]有序而n就是整个数组所以排序完成。这个过程配合while里的移动逻辑就能严格证明算法正确。实际解题时很多人会忽略证明中的“保持”环节里对“原数组元素”的理解。移动不会凭空产生或删除元素它只是改变元素的位置所以A[1..j]始终是原始前j个元素的一种排列。这个事实虽然直观但在严谨证明里必须写出来否则后续归纳会缺一环。5. 课后习题精讲常见答案与考试里容易丢分的地方5.1 习题2.2-1渐近记号的化简题目通常要求用Θ记号表示函数n³/1000 - 100n² - 100n 3的增长量级。答案很简单Θ(n³)。不过我想展开的不是答案本身而是为什么能直接丢掉低阶项和系数。根据Θ记号的定义我们需要找到正的常数c1、c2和n0使得对足够大的n有c1·n³ ≤ f(n) ≤ c2·n³。当n很大时n³项的增长速度碾压n²和n项所以低阶项和系数都不影响主项。这个例子是为了训练你一眼识别“最高次项决定量级”的能力。常见的错误是写成“O(n³)”。严格来说O记号只给出上界Θ给出的是上下界夹住。这道题用Θ更准确因为它不仅说你不会超过n³量级还说你的增长速度不会慢于n³量级。在后面的第2.3节“设计算法”里你会发现给出紧的上下界对比较算法优劣至关重要。5.2 习题2.2-2选择排序的正确性分析与运行时间这道题让写选择排序的伪代码证明正确性并分析最好和最坏运行时间。我给出一个参考实现SELECTION-SORT(A) 1 for i 1 to A.length - 1 2 minIndex i 3 for j i 1 to A.length 4 if A[j] A[minIndex] 5 minIndex j 6 交换 A[i] 与 A[minIndex]循环不变式可以这样写在每次外层循环开始前A[1..i-1]是数组中最小的i-1个元素并且已经有序同时A[i..n]包含剩余的元素。初始化时i1前缀为空性质平凡成立。保持阶段内层循环在A[i..n]中找到最小元素的下标minIndex然后与A[i]交换。由于前缀里已经是更小的元素这个最小元素比前缀里所有元素都大或相等所以交换后A[1..i]依然有序。终止时i A.length也就是处理到倒数第二个元素此时A[1..n-1]已包含最小的n-1个元素且有序最后一个元素自然是最大的所以A[1..n]有序。这里有个易错点为什么外层只循环到n-1而不是最后再处理一次我在初学的时候也纠结过。答案是经过n-1轮选择后剩下的那个元素不可能比已排好的n-1个元素更小它唯一能待的位置就是末尾。多处理一轮没有意义反而会引入无谓的交换。运行时间方面无论输入是否有序内层循环都必须扫描剩余区间找出最小值比较次数永远是n(n-1)/2。所以选择排序的最好和最坏情况都是Θ(n²)。这一点和插入排序形成鲜明对比插入排序在最好情况下是线性选择排序却永远要全量扫描。原因是选择排序“找最小值”这个操作无法从有序性中获益除非引入额外的数据结构比如堆。5.3 习题2.2-3线性搜索的平均与最坏检查次数题目问的是在线性搜索中平均情况下需要检查输入序列中的多少个元素最坏情况呢假设待查找元素等可能地出现在序列的任意位置。最坏情况很简单如果目标根本不出现或者出现在最后一个位置需要检查n个元素。但题目默认元素一定在序列中所以最坏是位置n检查次数为n。平均情况的计算是把所有位置的概率加起来加权。如果目标以相同概率出现在位置1到n那么期望检查次数是(12...n)/n(n1)/2。这个结果很多人会直觉猜是n/2实际上因为位置从1开始计数平均恰好是(n1)/2。n很大时它约等于n/2但严格推导时还是要写对。如果目标不一定存在那么平均检查和最坏检查又不一样。目标存在时检查次数是上面的期望目标不存在时必须检查完整个数组才能确认因此最坏情况是n平均也要接近n。实际代码里线性搜索常被用在无序小数组上因为它的常数很小而且对缓存友好。5.4 习题2.2-4让最佳情况“看起来更好”的小改动这道题有点开放性如何修改几乎所有算法使它们的最佳情况运行时间更好一个常见的思路是在算法开始前检查输入是否已经满足某种特殊条件。比如对插入排序可以在开头加一个线性扫描判断数组是否已经有序。如果已经有序直接返回这样最佳情况运行时间从Θ(n)改善为Θ(n)里的更小常数本质上仍然是线性但避免了一轮轮重复判断。严格来说渐近量级没有变化题目问的是“最佳情况运行时间”是否更好而修改后的最佳情况确实减少了很多常数开销。这个思路在工程里非常实用。很多复杂算法在实际数据上会先检查基线条件再决定走哪条分支。例如某些快速排序实现会在区间小于阈值时切换到插入排序并在递归入口检测“部分有序”的输入做一次预排序。这并不改变最坏情况的渐近复杂度但大幅优化了常见输入下的实际表现。从这道题可以引申出的教训是分析算法的渐近复杂度是必要的但绝不能替代对输入分布和常数因子的考虑。6. 理解插入排序分析时容易搞混的几个点6.1 O(n²)不是说一定跑n²步是增长的量级我见过很初学者拿着插入排序的O(n²)结论去算“n1000那就要跑100万步”这种理解是错的。O(n²)说的是当n趋于无穷时运行时间至多按n²的速度增长它不直接等于某个固定步数。严格的最坏情况表达式里n²前面的系数是c5/2c6/2c7/2低阶项还有一大堆。用Θ记号来看更清晰插入排序的最坏运行时间是Θ(n²)意思是存在正的上下界常数使得它在足够大的n上时间在a·n²和b·n²之间。这里a和b取决于每条指令的代价和硬件但跟n无关。所以我们通常说“增长量级是n²”而不是“就是n²”。我自己写代码时会把这种复杂度判断当成一种“数量级体检”数据翻一倍最坏时间大约翻四倍数据翻十倍时间大约翻一百倍。真正要预测量级可以用这个关系做快速估算然后通过实测校准常数。6.2 移动和比较是两件事先问瓶颈在哪个插入排序每次内层循环要做一次比较A[i]key如果条件成立再做一次移动A[i1]A[i]。比较次数决定while的循环次数移动次数等于比较次数减1。在分析里它们分别乘上c5、c6、c7所以在最坏情况下比较和移动的代价是同时增长的。但有些场景可以把比较和移动分开看。比如存储在链表里的元素移动的代价是O(1)的指针修改但比较依然是O(n)。又比如数组元素是比较大的结构体移动的代价远高于比较这时可以只移动下标最后统一写一次key这就是“延迟赋值”的思路也是某些优化版插入排序的做法。理解这两者是两件事才能针对具体场景做优化而不是看到n²就放弃。6.3 实际工程里插入排序并没有被扔进垃圾桶虽然插入排序的渐近复杂度不如归并排序和快速排序但它在小规模数据和近乎有序的数据上表现非常好。原因在于它的内部循环极简单没有递归调用没有额外的栈空间缓存局部性好常数因子非常小。很多生产级的排序库都把插入排序作为递归排序的“最后一公里”比如当递归区间长度小于16或32时就切换到插入排序。我曾在处理服务器端的一段日志排序时遇到过一个场景数据总量很大但每个分桶内部几乎是按时间顺序到达的只有少量数据错位。直接对分桶用快速排序反而比“先检查近似有序再对少量错位执行插入排序”慢。那个场景里插入排序的时间几乎接近线性而快速排序因为划分不均匀效率并不理想。从算法分析的角度看这件事儿的教训是不要被渐近复杂度吓住也不要迷信它。渐近分析告诉我们长期趋势常数因子和输入特征则决定短期和中等规模下的胜负。读《算法导论》第2.2节时如果能同时记住“分析是为了理解增长趋势”和“真实性能还要看常数”那么你才算真正把这个章节的内容消化成了自己的判断力。