选择排序

概述

选择排序是一种简单直观的比较排序算法，其核心思想是：每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的起始位置交换，直到所有元素有序。该算法的时间复杂度为$O(n^2)$，适用于小规模数据或教学演示，但在实际应用中效率低于快速排序或归并排序等高级算法。

算法特点

• 不稳定排序：相同元素的相对位置可能改变（例如对[5a, 2, 5b, 1]排序后可能变为[1, 2, 5b, 5a]）。
• 原地排序：仅需$O(1)$额外空间。
• 交换次数少：最多进行$n-1$次交换，优于冒泡排序的$O(n^2)$次交换。

算法步骤

选择排序的流程可分为以下步骤：

1. 从数组第1个元素开始，遍历未排序部分，找到最小元素的索引。
2. 将最小元素与当前未排序部分的起始位置交换。
3. 重复上述过程，每次未排序部分起始位置后移一位，直到数组完全有序。

flowchart TD A[开始] --> B[初始化 i = 0] B --> C{i < n-1?} C -->|是| D[设置 min_idx = i] D --> E[初始化 j = i+1] E --> F{j < n?} F -->|是| G{arr[j] < arr[min_idx]?} G -->|是| H[更新 min_idx = j] G -->|否| I[无操作] H --> J[j++] I --> J J --> F F -->|否| K[交换 arr[i] 和 arr[min_idx]] K --> L[i++] L --> C C -->|否| M[结束]

代码实现

以下是Python、Java和C语言的实现示例：

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 示例
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("排序结果:", data)  # 输出: [11, 12, 22, 25, 64]

Java

public class SelectionSort {
    void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22, 11};
        new SelectionSort().sort(data);
        System.out.println(Arrays.toString(data));  // 输出: [11, 12, 22, 25, 64]
    }
}

C语言

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int data[] = {64, 25, 12, 22, 11};
    int size = sizeof(data) / sizeof(data[0]);
    selectionSort(data, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i]);  // 输出: 11 12 22 25 64
    }
    return 0;
}

复杂度分析

选择排序的复杂度

情况	时间复杂度	说明
最优情况	$O(n^2)$	无论输入是否有序都需要完整比较
最差情况	$O(n^2)$
平均情况	$O(n^2)$
空间复杂度	$O(1)$	原地排序

实际应用场景

虽然选择排序效率不高，但在以下场景仍有应用价值：

• 嵌入式系统：内存受限环境需要简单算法时。
• 教学演示：作为排序算法的入门示例。
• 小规模数据：当$n<1000$时性能差异可忽略。
• 交换成本高的场景（如对存储在磁盘的大对象排序）。

变体与优化

双向选择排序

同时查找最小和最大元素，减少一半迭代次数：

def bidirectional_selection_sort(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        min_idx, max_idx = left, right
        for i in range(left, right + 1):
            if arr[i] < arr[min_idx]:
                min_idx = i
            elif arr[i] > arr[max_idx]:
                max_idx = i
        arr[left], arr[min_idx] = arr[min_idx], arr[left]
        if max_idx == left:  # 防止最大值被交换到min_idx位置
            max_idx = min_idx
        arr[right], arr[max_idx] = arr[max_idx], arr[right]
        left += 1
        right -= 1

使用堆结构优化

通过堆结构可将选择最小元素的时间从$O(n)$优化到$O(\log n)$，此时算法变为堆排序，时间复杂度提升至$O(n\log n)$。

常见问题

为什么选择排序不稳定？

当最小元素与前方元素交换时，可能跨越中间相同元素。例如对[3, 4, 3a, 2]：

1. 第一轮交换3和2 → [2, 4, 3a, 3]
2. 此时两个3的相对顺序已改变。

选择排序和冒泡排序哪个更快？

虽然两者时间复杂度相同，但选择排序的交换次数恒为$O(n)$，而冒泡排序在最差情况下需要$O(n^2)$次交换。因此选择排序通常实际运行更快。