排序算法之选择排序详细解读（附带Java代码解读）

本文主要是介绍排序算法之选择排序详细解读（附带Java代码解读），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择排序（Selection Sort）是一种简单且直观的排序算法。它的基本思想是：每一轮从未排序的部分中选出最小（或最大）的元素，放到已排序部分的末尾。通过不断地选择最小（或最大）元素，最终使整个数组有序。

算法思想

初始化：将数组分为已排序部分和未排序部分。开始时，已排序部分为空，未排序部分是整个数组。
选择最小元素：在未排序部分中找到最小的元素，并将其与未排序部分的第一个元素交换。这样，最小元素就被放到了已排序部分的末尾。
重复步骤2：不断重复上述过程，直到未排序部分为空。此时，整个数组已经有序。

过程示例

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

初始状态:

数组：[64, 25, 12, 22, 11]

第1轮选择:

在未排序部分 [64, 25, 12, 22, 11] 中，找到最小的元素 11。
将 11 和未排序部分的第一个元素 64 交换。
数组变为：[11, 25, 12, 22, 64]，其中 [11] 是已排序部分，[25, 12, 22, 64] 是未排序部分。

第2轮选择:

在未排序部分 [25, 12, 22, 64] 中，找到最小的元素 12。
将 12 和未排序部分的第一个元素 25 交换。
数组变为：[11, 12, 25, 22, 64]，其中 [11, 12] 是已排序部分，[25, 22, 64] 是未排序部分。

第3轮选择:

在未排序部分 [25, 22, 64] 中，找到最小的元素 22。
将 22 和未排序部分的第一个元素 25 交换。
数组变为：[11, 12, 22, 25, 64]，其中 [11, 12, 22] 是已排序部分，[25, 64] 是未排序部分。

第4轮选择:

在未排序部分 [25, 64] 中，找到最小的元素 25。
将 25 和未排序部分的第一个元素 25 交换（自身交换，数组不变）。
数组变为：[11, 12, 22, 25, 64]，其中 [11, 12, 22, 25] 是已排序部分，[64] 是未排序部分。

第5轮选择:

最后一轮只有一个元素 64，已是最小，不需要交换。
数组最终变为：[11, 12, 22, 25, 64]。

经过上述5轮选择，数组已经完全有序。

算法复杂度

时间复杂度:
- 最坏情况: O(n^2)
- 平均情况: O(n^2)
- 最佳情况: O(n^2)
选择排序在最优、最坏、和平均情况下的时间复杂度都是 O(n^2)，因为无论数组是否已排序，算法都要遍历整个未排序部分来寻找最小元素。
空间复杂度: O(1) 选择排序是原地排序算法，不需要额外的存储空间，只有一些临时变量用于交换。

优点

简单直观：选择排序的思想容易理解，实现起来也很简单。
交换次数较少：相比于冒泡排序，选择排序在数据量较大时，交换次数相对较少。

缺点

时间复杂度较高：无论数组是否已经部分有序，选择排序都需要进行 n(n-1)/2 次比较，因此时间复杂度较高，效率低。
不稳定：选择排序是一个不稳定的排序算法，如果两个相同的元素在数组中，他们在排序后可能会出现相对位置的变化。

选择排序的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 + " ");}}
}

代码说明

selectionSort方法:
- 外层循环遍历数组，从第一个元素开始。
- 假设当前位置的元素是最小值，记录它的索引 minIndex。
- 内层循环从当前位置的下一个元素开始，查找更小的元素，如果找到，则更新 minIndex。
- 内层循环结束后，交换 minIndex 对应的元素和当前元素的位置。
main方法:
- 创建一个待排序的数组 arr。
- 调用 selectionSort 方法对数组进行排序。
- 输出排序前和排序后的数组。