Question

算法导论的一个小问题

下图给出了这个算法在数组 A = <5， 2， 4， 6， 1， 3>上的工作过程。下标 j 指示了待插入的元素。在外层 for 循环的每一轮迭代开始时，包含元素 A [ 1 .. j - 1 ]的子数组就已经是排好序的了。

不太懂为什么，包含的元素 A [ 1 .. j - 1 ]的子数组就已经是排好序的了？ 元素不应该是有A[1..j ]的么？

Answer 1

你说的插入排序的算法吧？

文中说，下标 j 指示了待插入的元素。在外层 for 循环的每一轮迭代开始时，包含元素 A [ 1 .. j - 1 ]的子数组就已经是排好序的了。

这句话是没有问题的，你大概没有读懂。

插入排序没循环一轮就使得多一个数字排好序，所以第j轮循环之后，前面j个数字，也就是A[1..j ]已经是排好序的了。
但是，注意文中说的是“在外层 for 循环的每一轮迭代开始时”，也就是说在第j轮循环还没有进行时，那当然只有j-1个数字是排好序的了。所以，包含的元素 A [ 1 .. j - 1 ]的子数组就已经是排好序的了。