一.选择排序（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²)排序算法更有效。然而，它的效率不如更复杂的排序算法（如快速排序、归并排序）高。选择排序适合用于小规模数据集或对稳定性要求不高的场合。