【算法基础】选择排序算法 - JAVA

一、算法基础

1.1 什么是选择排序

选择排序是一种简单直观的排序算法，它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1.2 选择排序的基本思想

选择排序的核心思想是：

• 将输入数据分为已排序区域和未排序区域
• 不断从未排序区域选择最小元素，放入已排序区域的末尾
• 重复上述过程直到全部排序完成

1.3 时间复杂度

选择排序的时间复杂度分析如下：

• 最好情况时间复杂度：O(n²)
• 最坏情况时间复杂度：O(n²)
• 平均时间复杂度：O(n²)

无论输入数据是否已经部分排序，选择排序始终需要进行 n(n-1)/2 次比较，因此其时间复杂度总是 O(n²)。

1.4 空间复杂度

选择排序是一种原地排序算法，它只需要一个用于交换的临时变量，因此空间复杂度为 O(1)。

二、Java实现

2.1 基础实现

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;}}// 将找到的最小值与未排序区域的第一个元素交换if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}// 测试代码public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};selectionSort(arr);System.out.println("排序后的数组：");for (int i : arr) {System.out.print(i + " ");}}
}

2.2 算法步骤解析

1. 初始状态：整个数组视为未排序区域
2. 第一次迭代：
   • 在整个数组中找到最小元素
   • 将其与数组第一个元素交换位置
   • 数组第一个元素现在位于正确位置
3. 第二次迭代：
   • 从第二个元素开始，在剩余未排序元素中找到最小值
   • 将其与数组第二个元素交换位置
4. 重复过程：继续执行，直到所有元素都排序完毕

三、选择排序的特点

3.1 优点

• 实现简单，易于理解和编码
• 交换次数少：每次内循环只需要进行一次交换操作，最多进行 n-1 次交换
• 原地排序：不需要额外的存储空间
• 稳定性可控：可以实现为稳定排序算法（通过特定实现方式）

3.2 缺点

• 时间效率低：无论输入如何，时间复杂度始终为 O(n²)
• 不适合大规模数据：当数据量大时，性能显著下降
• 不会提前终止：即使数组已经排序，算法仍会执行完所有步骤

四、算法优化方案

4.1 双向选择排序

双向选择排序在每次迭代中同时查找最小值和最大值，减少了循环次数：

public static void bidirectionalSelectionSort(int[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;// 找出最小值和最大值for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[minIndex]) {minIndex = i;}if (arr[i] > arr[maxIndex]) {maxIndex = i;}}// 将最小值放到左边if (minIndex != left) {int temp = arr[left];arr[left] = arr[minIndex];arr[minIndex] = temp;// 如果最大值是left，那么交换后最大值位置变为minIndexif (maxIndex == left) {maxIndex = minIndex;}}// 将最大值放到右边if (maxIndex != right) {int temp = arr[right];arr[right] = arr[maxIndex];arr[maxIndex] = temp;}left++;right--;}
}

4.2 使用堆数据结构

可以使用最小堆来优化选择排序：

1. 构建一个最小堆 O(n)
2. 依次取出堆顶元素 O(log n)

这种方法实际上就是堆排序，时间复杂度降低到 O(n log n)。

五、实例分析

5.1 示例数组排序过程

以数组 [64, 25, 12, 22, 11] 为例：

1. 第一次迭代：
   • 找到最小值 11（索引 4）
   • 交换11和64：[11, 25, 12, 22, 64]
   • 已排序：[11]，未排序：[25, 12, 22, 64]
2. 第二次迭代：
   • 在剩余部分找到最小值 12（索引 2）
   • 交换12和25：[11, 12, 25, 22, 64]
   • 已排序：[11, 12]，未排序：[25, 22, 64]
3. 第三次迭代：
   • 在剩余部分找到最小值 22（索引 3）
   • 交换22和25：[11, 12, 22, 25, 64]
   • 已排序：[11, 12, 22]，未排序：[25, 64]
4. 第四次迭代：
   • 在剩余部分找到最小值 25（索引 3）
   • 不需要交换（已在正确位置）
   • 已排序：[11, 12, 22, 25]，未排序：[64]
5. 排序完成：[11, 12, 22, 25, 64]

5.2 性能分析

对比不同输入规模的性能表现：

• 小规模数据（n ≤ 50）：选择排序性能可接受
• 中等规模数据（50 < n ≤ 1000）：性能明显下降
• 大规模数据（n > 1000）：性能严重下降，不推荐使用

六、应用场景

6.1 适用场景

• 小规模数据排序：当数据量较小时，选择排序简单易实现
• 对交换操作敏感的场景：选择排序的交换次数最多为 n-1 次
• 辅助教学：作为排序算法的基础教学示例
• 内存受限的嵌入式系统：实现简单且空间复杂度低

6.2 不适用场景

• 大规模数据排序：性能太低，应选择更高效的算法
• 几乎已排序的数据：选择排序无法利用数据的部分有序性

七、总结

选择排序是一种简单直观的排序算法，核心思想是不断从未排序区域中选择最小元素放入已排序区域。

核心要点：

• 时间复杂度始终为 O(n²)，无论输入如何
• 空间复杂度为 O(1)，是一种原地排序算法
• 交换次数较少，最多进行 n-1 次交换
• 实现简单，代码易于理解和编写
• 对于大型数据集不推荐使用

选择排序虽然不是最高效的排序算法，但它的简单性和低空间复杂度使其在特定场景下仍有价值。对于编程初学者来说，理解选择排序有助于掌握排序算法的基本概念及其实现方法。