选择排序

算法定义

选择排序（Selection Sort）是一种简单直观的排序算法，它的核心思想是每次从待排序的元素中选出最小（或最大）的元素，将其放置在已排序序列的末尾，直到所有元素都排序完毕。

算法思路

选择排序的步骤非常直接：

从待排序数组的起始位置开始，找出整个数组中的最小元素。
将最小元素与数组的起始位置元素交换。
排除起始位置外的剩余元素（待排序部分），重复步骤 1 和 2，直到所有元素都被排序。

简单来说，就是通过不断选择剩余元素中的最小值来构建有序序列。

算法复杂度

最好时间复杂度：O (n²) - 即使数组已经有序，仍需遍历所有元素寻找最小值
最坏时间复杂度：O (n²) - 数组逆序时，比较和交换次数与最好情况相同
平均时间复杂度：O(n²)
空间复杂度：O (1) - 只需要一个临时变量用于交换元素，属于原地排序

优点与缺点

优点：
- 实现简单，逻辑清晰，易于理解和编码
- 原地排序，空间复杂度低（O (1)）
- 交换次数少（最多 n-1 次），适合交换成本高的场景
缺点：
- 时间复杂度高（O (n²)），不适合大规模数据排序
- 不稳定的排序算法（相等元素的相对位置可能改变）
- 无论输入数据是否有序，时间复杂度都固定为 O (n²)

应用场景

小规模数据的排序场景
对内存使用限制严格的环境（只需要常数级额外空间）
教学场景（理解简单排序算法的基本思想）
元素交换成本较高，但比较成本较低的场景（选择排序交换次数少）

各版本优化说明

基本版：
- 最经典的实现方式，每次从剩余元素中选择最小值
- 逻辑简单，但效率较低，适合理解选择排序的基本原理
双向选择排序：
- 每次遍历同时寻找最小值和最大值
- 将最小值放到左侧，最大值放到右侧，减少一半的外循环次数
- 对于大规模数组，实际运行效率比基本版提高约一倍
优化比较次数版本：
- 在内层循环中一次比较两个相邻元素，减少比较次数
- 先找出两个元素中的较小者，再与当前最小值比较
- 理论上可减少约一半的比较操作

选择排序虽然时间复杂度较高，但由于其实现简单、空间开销小，在一些对性能要求不高的小规模数据排序场景中仍有应用价值。与冒泡排序相比，选择排序的交换次数更少，在交换成本较高的场景下表现更优。

代码

import java.util.Arrays;

public class SelectionSort {
    
    // 1. 基本版选择排序（升序，每次选最小值）
    public static void selectionSortBasic(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        // 外层循环控制已排序部分的末尾位置
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 记录最小值的索引
            
            // 内层循环寻找剩余元素中的最小值
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小值索引
                }
            }
            
            // 将找到的最小值与当前位置元素交换
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }
    
    // 2. 优化版1：双向选择排序（同时找最小值和最大值）
    public static void selectionSortBidirectional(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int left = 0;
        int right = arr.length - 1;
        
        while (left < right) {
            int minIndex = left;  // 最小值索引
            int maxIndex = right; // 最大值索引
            
            // 在[left, right]范围内寻找最小值和最大值
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            
            // 将最小值交换到左侧
            if (minIndex != left) {
                swap(arr, left, minIndex);
            }
            
            // 处理最大值索引可能被交换的情况
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            
            // 将最大值交换到右侧
            if (maxIndex != right) {
                swap(arr, right, maxIndex);
            }
            
            left++;
            right--;
        }
    }
    
    // 3. 优化版2：减少比较次数的选择排序
    public static void selectionSortOptimizedCompare(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            // 在内层循环中同时处理两个元素的比较
            for (int j = i + 1; j < n; j += 2) {
                // 处理最后一个可能的奇数元素
                if (j + 1 > n - 1) {
                    if (arr[j] < arr[minIndex]) {
                        minIndex = j;
                    }
                    break;
                }
                
                // 比较相邻的两个元素，先找出较小的那个
                int smaller = (arr[j] < arr[j + 1]) ? j : j + 1;
                // 再与当前最小值比较
                if (arr[smaller] < arr[minIndex]) {
                    minIndex = smaller;
                }
            }
            
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }
    
    // 交换数组中两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 5};
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        
        selectionSortBasic(arr1);
        System.out.println("基本版: " + Arrays.toString(arr1));
        
        selectionSortBidirectional(arr2);
        System.out.println("双向选择排序: " + Arrays.toString(arr2));
        
        selectionSortOptimizedCompare(arr3);
        System.out.println("优化比较次数: " + Arrays.toString(arr3));
    }
}