Java中常用算法之选择排序算法

一.选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序部分选择最小（或最大）的元素，并将其放到已排序部分的末尾。以下是用Java实现选择排序的代码及其详细讲解。

二.选择排序代码

public class SelectionSort {public static void selectionSort(int[] array) {int n = array.length;// 外层循环遍历数组的每个元素for (int i = 0; i < n - 1; i++) {// 假设当前元素是未排序部分的最小值int minIndex = i;// 内层循环寻找未排序部分的最小值for (int j = i + 1; j < n; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}// 将找到的最小值与未排序部分的第一个元素交换int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}public static void main(String[] args) {int[] array = {64, 25, 12, 22, 11};System.out.println("Unsorted array:");printArray(array);selectionSort(array);System.out.println("Sorted array:");printArray(array);}private static void printArray(int[] array) {for (int value : array) {System.out.print(value + " ");}System.out.println();}
}

三.详细讲解

1. 初始化:

• n是数组的长度。

2. 外层循环:

• 遍历数组的每个元素，i表示当前已排序部分的末尾。

• 假设当前元素array[i]是未排序部分的最小值，初始化minIndex为i。

3. 内层循环:

• 从i+1开始遍历未排序部分，寻找最小值。

• 如果找到比当前最小值array[minIndex]更小的元素，则更新minIndex。

4. 交换元素:

• 将找到的最小值array[minIndex]与未排序部分的第一个元素array[i]交换。

• 使用一个临时变量temp来交换两个元素的位置。

5. 打印数组:

• printArray方法用于打印数组的内容。

总结

选择排序的时间复杂度为O(n²)，因为在最坏情况下需要进行n²次比较。选择排序的优点是它的实现简单，并且在某些情况下（如内存写入次数较少时）可能比其他O(n²)排序算法更有效。然而，它的效率不如更复杂的排序算法（如快速排序、归并排序）高。选择排序适合用于小规模数据集或对稳定性要求不高的场合。