每一趟从未排序区间里选择最小值，并交换到当前起始位置。

Ph1zの理解： 选择排序就像排队——每次从剩下的人里挑最矮的，站到队首。简单吧？但每次挑人都要扫一遍，所以效率不高。

代码

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[minIndex]) minIndex = j;
        }
        if (minIndex != i) std::swap(a[i], a[minIndex]);
    }
}

正确性证明

循环不变式： 在第 i 轮开始前，前 i 个位置已经放置了最小的 i 个元素，且它们按排序要求排列。

• 初始化： i = 0 无前元素，成立。
• 保持： 在未排序区间中选出最小值 m，把它交换到第 i 位，因此前 i + 1 个位置一定是当前最小的 i + 1 个元素。
• 终止： 当 i = n - 1 时，全部元素有序。 ✓

复杂度分析

外层循环做 $n-1$ 趟，每趟扫描剩余部分，复杂度为：

$$T(n)=\sum _{i=0}^{n-1}(n-i-1)=\frac{n(n-1)}{2}=O(n^2).$$

注意： 选择排序的最好、平均、最坏全是 $O(n^2)$——它不像插入排序有"最好 $O(n)$"的福利，因为不管数组多有序，每趟都得扫完剩余部分才能确定最小值。

空间复杂度： $O(1)$。

稳定性： 不稳定。原因是交换最小值时，可能把与它相等的元素从后面交换到前面，打乱相对顺序。

反例： [5a, 5b, 3]，第一趟选出最小值 3 与 5a 交换 → [3, 5b, 5a]，两个 5 的相对顺序变了。