选择排序

基本介绍

选择排序(select sorting)也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…，第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

代码实现

// 选择排序，时间复杂度 O(n^2)
public static void selectSort(int[] arr) {
    int min; // 记录最小值
    int minIndex; // 记录交最小值的位置位置
    for (int start = 0; start < arr.length - 1; start++) {
        min = arr[start];
        minIndex = start;
        for (int i = start; i < arr.length - 1; i++) {
            if (arr[i + 1] < min) {
                min = arr[i + 1];
                minIndex = i + 1;
            }
        }
        if (minIndex != start) {
            arr[minIndex] = arr[start];
            arr[start] = min;
        }
    }
}