Java 排序算法之选择排序

选择排序（Selection Sort）算法是一种简单直观的排序算法，它的基本思路是在未排序序列中找到最小元素，然后将其存放到序列的起始位置，然后再从剩余未排序的序列中继续寻找最小元素，存放到已排序序列的末尾。以此类推，直到全部元素均排序完成。

排序过程

以从小到大排序为例，选择排序的一次过程如下：

1. 从待排序的序列中，找到关键字最小的元素；
2. 如果该最小元素不是序列的第一个元素，也不是当前无序区的第一个元素，则将其位置和序列的第一个元素交换位置；
3. 从剩余的关键字中继续寻找最小的元素；
4. 重复步骤2，直到所有元素均排序完成。

代码示例

以下是 Java 代码示例：

public static void selectionSort(int[] arr) {
    int len = arr.length;
    int minIndex, temp;
    for (int i = 0; i < len - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

示例说明

以下是对代码示例的两条说明：

示例 1

假设要排序的数组为 {3, 1, 4, 2, 5}，初始状态下，数组元素的排序状态如下：

3 1 4 2 5

选择排序的第一轮排序过程如下：

1. 从数组中找到最小值为 1，其下标为 1；
2. 将元素 3 和元素 1 交换，数组状态变为：

1 3 4 2 5

选择排序的第二轮排序过程如下：

1. 从数组中找到最小值为 2，其下标为 3；
2. 将元素 3 和元素 2 交换，数组状态变为：

1 2 4 3 5

选择排序的第三轮排序过程如下：

1. 从数组中找到最小值为 3，其下标为 3；
2. 由于元素 3 已经在正确的位置上，因此无需交换，数组状态不变：

1 2 3 4 5

选择排序的第四轮排序过程如下：

1. 从数组中找到最小值为 4，其下标为 3；
2. 将元素 4 和元素 4 交换，数组状态不变：

1 2 3 4 5

选择排序的第五轮排序过程如下：

1. 从数组中找到最小值为 5，其下标为 4；
2. 将元素 5 和元素 5 交换，数组状态不变：

1 2 3 4 5

因为数组已经排好序，所以选择排序结束。

示例 2

假设要排序的数组为 {10, 7, 8, 9, 1, 5}，初始状态下，数组元素的排序状态如下：

10 7 8 9 1 5

选择排序的第一轮排序过程如下：

1. 从数组中找到最小值为 1，其下标为 4；
2. 将元素 10 和元素 1 交换，数组状态变为：

1 7 8 9 10 5

选择排序的第二轮排序过程如下：

1. 从数组中找到最小值为 5，其下标为 5；
2. 将元素 10 和元素 5 交换，数组状态变为：

1 7 8 9 5 10

选择排序的第三轮排序过程如下：

1. 从数组中找到最小值为 7，其下标为 1；
2. 将元素 7 和元素 7 交换，数组状态不变：

1 7 8 9 5 10

选择排序的第四轮排序过程如下：

1. 从数组中找到最小值为 8，其下标为 2；
2. 将元素 8 和元素 8 交换，数组状态不变：

1 7 8 9 5 10

选择排序的第五轮排序过程如下：

1. 从数组中找到最小值为 9，其下标为 3；
2. 将元素 9 和元素 9 交换，数组状态不变：

1 7 8 9 5 10

因为数组还没有排好序，所以需要进行第二轮排序。

选择排序的第六轮排序过程如下：

1. 从数组中找到最小值为 5，其下标为 4；
2. 将元素 7 和元素 5 交换，数组状态变为：

1 5 8 9 7 10

选择排序的第七轮排序过程如下：

1. 从数组中找到最小值为 7，其下标为 4；
2. 将元素 8 和元素 7 交换，数组状态变为：

1 5 7 9 8 10

选择排序的第八轮排序过程如下：

1. 从数组中找到最小值为 8，其下标为 4；
2. 将元素 9 和元素 8 交换，数组状态变为：

1 5 7 8 9 10

因为数组已经排好序，所以选择排序结束。