插入排序最坏情况运行时间疑问：长度为5的数组比较次数

别担心，这个问题完全适合在这里提问！你提到的O(n²)是渐近时间复杂度，它描述的是当数据规模n趋向于无穷大时算法的增长趋势，并不是实际的比较次数，所以直接用5²=25来计算是不准确的哦。

插入排序最坏情况的场景 #

插入排序的最坏情况出现在数组完全逆序的时候（比如[5,4,3,2,1]），这时候每一个新元素都需要和前面所有已经排好序的元素逐一比较。

具体计算长度为5的数组的比较次数 #

我们可以逐个元素分析：

• 第2个元素（4）：需要和前面1个元素比较，共1次
• 第3个元素（3）：需要和前面2个元素比较，共2次
• 第4个元素（2）：需要和前面3个元素比较，共3次
• 第5个元素（1）：需要和前面4个元素比较，共4次

把这些次数加起来：1+2+3+4=10次。

通用公式推导 #

对于长度为n的数组，插入排序最坏情况的比较次数是求和公式n(n-1)/2，当n=5时就是5*4/2=10次。而O(n²)是因为这个公式的最高次项是n²/2，渐近复杂度会忽略常数系数和低次项，所以用O(n²)来描述它的时间复杂度。

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