选择排序

定义与基本思想

选择排序（Selection Sort）是一种简单直观的排序方法。其基本思想是：每一趟从待排序序列中选出最小（或最大）元素，放到已排序序列的末尾，直到全部有序。

选择排序

点击“执行一步”观察算法状态变化。

算法描述

每一趟在未排序部分选出最小元素，与未排序部分第一个元素交换
重复 $n-1$ 趟，直到全部有序

伪代码如下：

for i = 0 to n-2:
    min = i
    for j = i+1 to n-1:
        if A[j] < A[min]:
            min = j
    if min != i:
        swap(A[i], A[min])

代码实现

void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;                     // 记录最小元素下标
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min]) min = j;  // 找到更小元素
        }
        if (min != i) {                  // 交换到已排序区末尾
            int tmp = A[i];
            A[i] = A[min];
            A[min] = tmp;
        }
    }
}

与堆排序的关联

简单选择排序每次都要遍历剩余部分找最小元素，比较次数恒为 $\frac{n(n-1)}{2}$ 。堆排序正是利用”堆”这种结构，把”找最小元素”的时间从 $O(n)$ 优化到 $O(\log n)$ ，从而将整体复杂度从 $O(n^2)$ 降到 $O(n\log n)$ 。

时间复杂度分析

最好/最坏/平均情况： $O(n^2)$
空间复杂度： $O(1)$
稳定性：不稳定排序

习题

习题 1

对数组 $A = [64, 25, 12, 22, 11]$ 进行选择排序，写出每一趟排序后的结果。

参考答案

选择排序排序过程最小元素

解题思路：

本题考查选择排序的执行过程。核心思想是每一趟从未排序区间中选出最小元素，与未排序区间的第一个位置交换，从而使有序前缀逐步扩大，直到全部元素有序。

详细步骤：

初始：[64, 25, 12, 22, 11]
第 1 趟：[11, 25, 12, 22, 64]
第 2 趟：[11, 12, 25, 22, 64]
第 3 趟：[11, 12, 22, 25, 64]
第 4 趟：[11, 12, 22, 25, 64]

最终答案：

如上，每一趟后最小元素归位。

习题 2

选择排序的时间复杂度和空间复杂度分别是多少？

参考答案

选择排序时间复杂度空间复杂度

解题思路：

本题考查选择排序的复杂度分析。选择排序共进行 $n-1$ 趟，每趟都要在未排序区间中扫描一遍寻找最小元素，故平均与最坏时间复杂度都是 $O(n^2)$ ；比较与交换都直接在原数组上进行，空间复杂度为 $O(1)$ 。

详细步骤：

时间复杂度 $O(n^2)$ ：共 $n-1$ 趟，每趟扫描未排序区间寻找最小元素，合计 $O(n^2)$ 次比较。
空间复杂度 $O(1)$ ：只需常数个辅助变量用于记录最小元素及其位置，不需要额外数组。
对比参考：堆排序的时间复杂度为 $O(n \log n)$ 、空间为 $O(1)$ ；归并排序的时间复杂度为 $O(n \log n)$ 、空间为 $O(n)$ 。