选择排序

概述

选择排序是一种简单直观的排序算法，其核心思想是：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。该算法通过重复这一过程直到所有元素有序。由于其在最坏和平均情况下的时间复杂度均为$O(n^2)$，适用于小规模数据排序，但对大规模数据效率较低。

算法步骤

选择排序的步骤如下（以升序为例）：

1. 初始状态：整个数组为未排序区，已排序区为空。
2. 第$i$轮（$i$从0开始）：
   1. 遍历未排序区，找到最小元素的索引$min\mathrm{\_}index$。
   2. 将未排序区的第一个元素与$min\mathrm{\_}index$位置的元素交换。
   3. 此时前$i+1$个元素构成已排序区。
3. 重复上述步骤，直到未排序区只剩一个元素。

动态示例

graph TD A[初始数组: 64 25 12 22 11] --> B[第1轮: 选择11与64交换] B --> C[结果: 11 | 25 12 22 64] C --> D[第2轮: 选择12与25交换] D --> E[结果: 11 12 | 25 22 64] E --> F[第3轮: 选择22与25交换] F --> G[结果: 11 12 22 | 25 64] G --> H[第4轮: 选择25（已在正确位置）] H --> I[最终排序结果: 11 12 22 25 64]

代码实现

以下是Python的实现示例：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 交换元素
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 示例
input_array = [64, 25, 12, 22, 11]
print("排序前:", input_array)
output_array = selection_sort(input_array)
print("排序后:", output_array)

输出结果:

排序前: [64, 25, 12, 22, 11]
排序后: [11, 12, 22, 25, 64]

关键点说明

• 外层循环控制已排序区的边界。
• 内层循环在未排序区中查找最小值。
• 每次交换后，已排序区长度增加1。

复杂度分析

时间复杂度

• 最坏情况：$O(n^2)$（逆序数组）
• 平均情况：$O(n^2)$
• 最好情况：$O(n^2)$（即使数组已有序仍需完整比较）

空间复杂度

• 原地排序，仅需常数级额外空间：$O(1)$

稳定性问题

选择排序是不稳定的排序算法。例如对数组[3a, 2, 3b, 1]（其中3a和3b值相同）排序时：

1. 第1轮：1与3a交换 → [1, 2, 3b, 3a]
2. 第2轮：2已在正确位置
3. 第3轮：3b与自身交换

最终结果中3a和3b的相对顺序改变。

优化方向

• 双向选择排序：同时查找最小值和最大值，减少交换次数。
• 堆排序：利用堆结构优化选择过程，时间复杂度可降至$O(n\log n)$。

实际应用场景

尽管效率不高，选择排序在以下场景仍有价值：

1. 小规模数据：代码简单，常数项小。
2. 内存受限环境：原地排序特性。
3. 需要最少交换次数：严格最多$n-1$次交换（优于冒泡排序）。

• 比冒泡排序更高效（减少交换次数）。
• 比插入排序更适用于元素移动成本高的场景（如链表排序）。

练习建议

1. 尝试用选择排序降序排列数组。 2. 实现双向选择排序版本。 3. 分析选择排序在链表结构上的适用性。