选择排序

简介

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从未排序区中选择最小（或最大）的元素，放置到已排序区的末尾（或开头），以此逐步构建有序区间。

算法步骤

选择排序的算法步骤如下：

• 将数组分为已排序区和未排序区，初始时已排序区为空。

• 在未排序区中找到最小（或最大）的元素，将其与未排序区的第一个元素交换位置，将该元素放置到已排序区的末尾（或开头）。

• 不断重复步骤2，直到未排序区为空，完成排序。

实现示例

以下是一个使用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;
                }
            }
            swap(array, i, minIndex);
        }
    }
​
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
​
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6, 3, 9};
        System.out.println("Original array: " + Arrays.toString(array));
        selectionSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

在上面的代码中，selectionSort方法实现了选择排序算法。它使用了两个嵌套的循环，外层循环用于控制已排序区的末尾位置，内层循环用于在未排序区中找到最小元素的索引。通过不断交换找到的最小元素与已排序区末尾元素的位置，逐步构建有序区间。

在main方法中，我们创建一个整数数组并进行选择排序。运行程序后，将输出原始数组和排序后的数组。