宝藏速成秘籍（3）选择排序法

一、前言

1.1、概念

选择排序法（Selection Sort）是一种简单直观的排序算法。它的基本思想是：每次从待排序的数组中选择最小（或最大）的元素，将其放在已排序部分的末尾，直到所有元素都排序完毕。

1.2、排序步骤

1.初始化已排序部分和未排序部分：
- 初始状态下，整个数组为未排序部分。
- 已排序部分为空。

2.从未排序部分找到最小（或最大）元素：
- 在未排序部分中查找最小（或最大）的元素。
- 将该元素的索引保存下来。

3.交换元素：
- 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。

4.更新已排序部分和未排序部分：
- 将未排序部分的第一个元素加入到已排序部分。
- 未排序部分从原来的第二个元素开始。

5.重复步骤2到4，直到所有元素都排序完毕。

二、方法分析

选择排序法逐步将最小元素移动到已排序部分的末尾，最终实现整个数组的排序。选择排序是一种简单且直观的排序算法，适用于小规模数据的排序任务。尽管它的时间复杂度较高，且不是稳定排序，但其实现和理解难度较低。在现代应用中，选择排序更多的是作为算法学习的入门工具，而不是实际排序任务的首选。

三、举例说明

假设有一个数组：[64, 25, 12, 22, 11]

#### 第一次迭代：
- 未排序部分：[64, 25, 12, 22, 11]
- 找到最小元素 11，与第一个元素 64 交换。
- 交换后数组：[11, 25, 12, 22, 64]
- 已排序部分：[11]
- 未排序部分：[25, 12, 22, 64]

#### 第二次迭代：
- 未排序部分：[25, 12, 22, 64]
- 找到最小元素 12，与第一个元素 25 交换。
- 交换后数组：[11, 12, 25, 22, 64]
- 已排序部分：[11, 12]
- 未排序部分：[25, 22, 64]

#### 第三次迭代：
- 未排序部分：[25, 22, 64]
- 找到最小元素 22，与第一个元素 25 交换。
- 交换后数组：[11, 12, 22, 25, 64]
- 已排序部分：[11, 12, 22]
- 未排序部分：[25, 64]

#### 第四次迭代：
- 未排序部分：[25, 64]
- 最小元素是 25，不需要交换。
- 已排序部分：[11, 12, 22, 25]
- 未排序部分：[64]

#### 第五次迭代：
- 只剩下一个元素 64，它已经在正确位置。
- 数组排序完成：[11, 12, 22, 25, 64]

四、编码实现

下面是选择排序法的 Java 实现：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        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;
                }
            }
            
            // 交换找到的最小元素与当前元素的位置
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        selectionSort(arr);
        
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

运行结果：

五、方法评价

### 时间复杂度
选择排序的时间复杂度为 O(n^2)，因为它有两个嵌套的循环，每个循环的时间复杂度为O(n)。
-最坏情况: O(n^2)
-最好情况: O(n^2)
-平均情况: O(n^2)

无论数组是否已排序，选择排序总是进行n(n-1)/2 次比较和最多 (n-1) 次交换。

### 空间复杂度
选择排序是一种原地排序算法，它的空间复杂度为 O(1)，因为它只使用了常数级别的额外空间。

### 稳定性
选择排序是一种不稳定的排序算法。例如，对于序列 [4, 3, 3, 1]，选择排序在第一次迭代中会将第一个 3 和 1 交换位置，从而破坏了两个 3 的相对顺序。

### 适用性
选择排序适用于数据量较小的情况，因为它的时间复杂度较高。对于大数据集，选择排序的效率较低，不适用于实际应用中的大规模排序任务。

### 优点
1.简单直观: 算法逻辑简单，容易理解和实现。
2.无需额外空间: 由于它是原地排序算法，不需要额外的存储空间。

### 缺点
1.时间复杂度高: O(n^2) 的时间复杂度在数据量较大时性能较差。
2.不稳定: 无法保证相同元素的相对顺序。