关于选择排序循环不变式的疑问：为何是A[1:i-1]而非A[1:i]？

先贴出选择排序的伪代码：

SELECTION SORT (A,n)
for i= 1 to n-1
    smallest=i
    for j=i+1 to n
        if A[j]<A[smallest]
                smallest=j
    exchange A[i] with A[smallest]

关于A[1:0]的含义 #

A[1:0]表示空数组，在数组索引规则中，当起始索引大于结束索引时，对应的子数组不包含任何元素。这是循环不变式必须覆盖的边界初始状态，完全符合逻辑。

为什么官方用A[1:i-1]而非A[1:i] #

循环不变式的核心是描述每次外层循环迭代开始前的数组状态，而非迭代结束后的状态：

• 当i=1时，第一次外层循环还未执行，没有任何元素被放到最终的正确位置，此时空数组A[1:0]天然满足“有序且包含数组前i-1个最小元素”的条件——空数组默认有序，也不存在需要验证的元素。
• 当执行完第i次外层循环后，A[i]会被替换为A[i:n]中的最小元素，此时A[1:i]才成为有序且包含前i个最小元素的子数组，但这是循环结束后的结果，不能作为循环开始前的不变式。

官方解决方案翻译（选择排序部分） #

选择排序的循环不变式：
在每次外层for循环的迭代开始时，子数组A[1..i-1]包含了数组A[1..n]中最小的i-1个元素，且该子数组已按升序排列。

证明过程：

1. 初始化：当i=1时，子数组A[1..0]为空，空数组满足“包含0个最小元素且有序”的条件，不变式成立。
2. 保持：假设第i次迭代开始时不变式成立，即A[1..i-1]是有序的最小i-1个元素。内层循环会找到A[i..n]中的最小元素并与A[i]交换，此时A[1..i]包含了数组中最小的i个元素，且依然有序（因为A[i]是剩余元素中的最小值，不小于A[1..i-1]的所有元素，而A[1..i-1]本身已经有序）。当i递增到i+1时，A[1..(i+1)-1] = A[1..i]满足不变式，因此不变式得以保持。
3. 终止：外层循环终止时i=n，此时A[1..n-1]是有序的最小n-1个元素，剩下的A[n]是最大元素，整个数组A[1..n]已完全有序。

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