选择排序主for循环为何执行n-1步而非n步？附C++实现代码

我尝试编写了一段选择排序的C++代码，经测试可返回有序数组，逻辑看起来正确，但我不太理解为什么排序的主for循环只需要执行n-1步，而不是n步？

#include <iostream>
using namespace std;
int main() {
    int a[10], k, i, j, n, aux;
    cin >> n;
    for (i = 0; i <= n-1; i++)
        cin >> a[i];
    k = a[0];
    for (i = 0; i <= n - 2; i++) {
        for (j = i + 1; j <= n-1; j++)
            if (k > a[j])
                k = a[j];
        for (j = i + 1; j <= n-1; j++)
            if (k == a[j]) {
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
            }
        k = a[i + 1];
    }
    for (i = 0; i <= n-1; i++)
        cout << a[i];
    return 0;
}

解答 #

这其实是选择排序的核心逻辑特性决定的，咱们来一步步拆解：

选择排序的核心思路是每一轮循环确定当前未排序区间里的最小（或最大）元素，把它放到未排序区间的起始位置。

假设你有一个长度为n的数组：

• 第1轮循环（i=0）：找到整个数组里的最小值，和第0位元素交换，此时第0位成为整个数组的最小值，属于已排序区间。
• 第2轮循环（i=1）：在第1位到第n-1位的未排序区间里找最小值，交换到第1位，前2位变为有序状态。
• ...
• 第n-1轮循环（i=n-2）：在第n-2位到第n-1位的区间里找最小值，交换到第n-2位，此时前n-1位都已经是有序的。

这时候你会发现，剩下的最后一个元素（第n-1位）根本不需要再处理了——因为前面n-1个元素已经是整个数组里最小的n-1个元素，最后一个元素自然就是最大的那个，它的位置已经完全正确。

如果强行执行第n轮循环（i=n-1），未排序区间就只剩下第n-1位这一个元素，找最小值、交换操作都没有任何意义，纯粹是做无用功。

回到你的代码里，主循环for (i = 0; i <= n - 2; i++)刚好执行了n-1次（i从0到n-2，一共是(n-2)-0+1 = n-1次），完美覆盖了所有需要确定位置的元素，最后一个元素自动归位，所以完全不需要执行n步。

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