为何插入排序伪代码中的外层for循环仅执行一次？

首先贴出你提供的插入排序伪代码：

for i <- 2,n do 
    aux <- v[i] 
    j <- i-1 
    while aux < v[j] AND j >= 0 do 
        v[j+1] <- v[j] 
        j <- j-1 
    end while
    v[j+1] <- aux 
end for

你的老师说外层for循环仅执行一次，只有两种合理的情况：

• 输入数组长度为2（n=2）
  此时外层循环的迭代范围是i从2到2，循环条件仅满足一次，自然只会执行一次外层循环。这是最直接的场景。

• 输入数组完全有序，老师做了简化表述
  正常插入排序的外层循环需要执行n-1次（从第2个元素遍历到第n个元素），但如果数组本身已经是完全有序的状态，每次外层循环里的while判断aux < v[j]都会直接不成立，不会进入元素移动的逻辑，只是把当前元素aux放回原位置。这种情况下，所有外层循环的执行都没有实际的排序操作，可能老师简化表述成“仅执行一次有效循环”，或是拿n=2的特例来讲解核心逻辑。

另外注意，这段伪代码的边界判断j >= 0如果对应1-based索引的数组可能存在问题（比如数组索引从1开始时，j的下限应该是1），但这和外层循环的执行次数无关。

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