选择排序

定义与基本思想

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

选择排序演示

6425122211

算法描述

每一趟在未排序部分选出最小元素，与未排序部分第一个元素交换
重复 $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

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

答案与解析

解题思路：考查复杂度和空间。

详细步骤：

时间复杂度 $O(n^2)$
空间复杂度 $O(1)$

答案：时间 $O(n^2)$ ，空间 $O(1)$ 。

上一章节冒泡排序介绍冒泡排序的基本思想、算法流程、复杂度分析及典型习题。

下一章节希尔排序介绍希尔排序的基本思想、算法流程、复杂度分析及典型习题。