算法之选择排序：最直观的排序哲学

紫风

发布于 2025-10-14 18:39:46

700

代码可运行

运行总次数：0

代码可运行

一、算法本质

选择排序如同精明的园丁挑选果实：

扫描果园：在未排序区域寻找最小的果实
摘下果实：将找到的最小值与当前位置交换
缩小范围：已排序区域向右扩展，重复这个过程

整个过程就像逐渐构建有序序列的拼图游戏，每次只确保当前拼块的位置正确。

二、Java实现（教学版）

public class SelectionSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 在未排序区寻找最小值
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 将最小值交换到已排序区末尾
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

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

三、性能分析

指标	数值	说明
时间复杂度	O(n²)	双重循环结构，比较次数固定
空间复杂度	O(1)	原地排序，无需额外空间

算法特性：

简单直观，适合教学理解
交换次数最少（仅需n-1次交换）
不稳定排序（相同元素可能改变顺序）

四、应用场景

教学演示：算法入门的最佳案例
小规模数据：当n<1000时性能尚可接受
写操作敏感场景：如EEPROM存储器（写寿命有限）
基础组件：某些硬件排序电路的实现基础

实际案例：

嵌入式设备的内存排序
游戏开发中的简单物品栏排序
机器学习特征选择时的初步排序

五、学习路线

新手必练：

手动模拟排序过程（纸上推演）
统计比较次数和交换次数
实现泛型版本（支持多种数据类型）

高手进阶：

双指针优化（同时找最大和最小值）
堆排序对比（选择排序的进化形态）
研究不稳定性问题与解决方案

// 优化版：同时找最大最小值
public static void dualSelectionSort(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int min = left, max = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min]) min = i;
            if (arr[i] > arr[max]) max = i;
        }
        swap(arr, left, min);
        if (max == left) max = min; // 处理最大值被交换的情况
        swap(arr, right, max);
        left++;
        right--;
    }
}