插入排序比较次数上限疑问：为何等于逆序数+数组长度-1？

先贴出参考的伪代码：

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

1. 额外的n-1次比较来源 #

这里的“额外比较”指不触发交换的条件判断。伪代码中内层循环的j > 0 and A[j-1] > A[j]每次执行都算一次比较：

• 触发交换的比较次数等于数组逆序数（每交换一次对应一对逆序对）。
• 当元素找到正确位置时，会多执行一次“终止比较”：此时A[j-1] <= A[j]，判断结果为假，内层循环终止。

对于长度为n的数组，我们需要处理n-1个元素（从i=1到i=n-1），最坏情况下每个元素都需要这一次终止比较，总共n-1次，这就是额外次数的来源。比如完全有序的数组，逆序数为0，总比较次数就是0 + (n-1)，刚好对应上限。

2. “当a[i]未到达数组左端时”的含义 #

这句话描述的是内层循环终止的典型场景：在将A[i]向左插入的过程中，还没移动到数组最左端（j>0），但已经遇到第一个不大于A[i]的元素A[j-1]，此时执行的那次比较（A[j-1] > A[j]为假）就是额外比较，直接终止循环。
比如有序数组中的每个元素A[i]，处理时j=i>0，比较A[j-1]和A[j]后发现不需要交换，此时A[i]仍在原位置（未到左端），循环终止，这就是这类场景的体现。

3. 数组1423的比较次数验证 #

拆解数组[1,4,2,3]的执行过程，统计所有比较次数：

• i=1（元素4）：j=1，比较1>4?，结果为假，内层循环终止。比较次数+1，交换次数0。
• i=2（元素2）：j=2，比较4>2?，结果为真，交换后j=1；再比较1>2?，结果为假，循环终止。比较次数+2，交换次数+1。
• i=3（元素3）：j=3，比较4>3?，结果为真，交换后j=2；再比较2>3?，结果为假，循环终止。比较次数+2，交换次数+1。

总比较次数=1+2+2=5。该数组的逆序数是2（逆序对为(4,2)、(4,3)），n-1=3，5=2+3，完全符合“比较次数=逆序数+额外次数”的规律。你觉得不符是误解了“额外次数固定为n-1”——实际上额外次数是每个元素可能贡献0或1次，总和最多为n-1，这个例子刚好达到上限，完全符合文献结论。伪代码中的内层循环条件判断本身就包含了这些不触发交换的比较，只是需要把所有条件判断都纳入计数，而非只统计触发交换的比较。

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