插入排序对6个元素排序耗时计算：最坏情况为何是30µs？

插入排序最坏情况的比较次数 #

插入排序在最坏情况（待排序列完全逆序）下，每个新元素都需要和前面所有已排序元素逐一比较。对于6个元素：

• 第2个元素：与前1个元素比较，共1次
• 第3个元素：与前2个元素比较，共2次
• 第4个元素：与前3个元素比较，共3次
• 第5个元素：与前4个元素比较，共4次
• 第6个元素：与前5个元素比较，共5次

总比较次数为：1+2+3+4+5=15 次。

30µs答案的推导 #

已知题目给出答案为30µs，结合“奇数次比较耗时2µs，偶数次比较耗时1µs”的条件，最合理的推导是：
题目中的“奇数次比较”表述存在歧义，实际应理解为在最坏情况下，所有比较操作均按奇数次比较的耗时计算（即每次比较耗时2µs）。此时总耗时为：
15次 × 2µs/次 = 30µs

另一种可能的解释是题目将“总比较次数为奇数”作为触发条件，由于总比较次数15是奇数，因此所有比较均按2µs计算，最终得到30µs。

如果严格按“第k次比较（k为奇数）耗时2µs，k为偶数耗时1µs”计算，总耗时应为：

• 奇数次比较（第1、3、5...15次）共8次：8×2=16µs
• 偶数次比较（第2、4、6...14次）共7次：7×1=7µs
• 总耗时：16+7=23µs，与给定答案不符，因此更倾向于题目表述存在歧义，实际按统一2µs/次计算。

内容的提问来源于stack exchange，提问作者Sheep_Walker