选择排序

定义与基本思想

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

选择排序演示

6425122211

下一步

算法描述

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

时间复杂度分析

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

练习题

练习 1

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

参考答案

解题思路：每趟选最小元素放到前面。

详细步骤：

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

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

练习 2

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

参考答案

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

详细步骤：

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

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