01选择排序

原理：

数组array = {2,15,7,9,30, 1, 5}

口语描述：找出最小（大）的放到第一个位置，再从剩下的数中找到最小（大）的放到第二个位置，再从剩下的数中找到最小（大）的放到第三个位置。。。。一直找到最后

假设最小值的下标为min（默认为0），

第一次：从array[0]开始，找到array[0]~array[n]最小的值：array[min]，
交换array[0] 和 array[min]。

第二次：从array[1]开始，找到array[1]~array[n]最小的值：array[min]，交换array[1] 和 array[min]。

第三次：从array[2]开始，找到array[2]~array[n]最小的值：array[min]，交换array[2] 和 array[min]。

。。。。。。
一直循环到倒数第二个即可

代码：

/**
 * 选择排序：最简单但是最没用的排序算法
 * 
 * */
public class Sort01_Select {
    
    public static void main(String[] args) {
        int[] array = {2,15,7,9,30, 1, 5};
        selectSort(array);
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
    

    /**
     * 时间复杂度：
     * 当数组长度为n时，i和j的取值范围以及循环次数：
     * 
     * 范围           |   次数
     * i∈[0, n-2]   |   n-1
     * --------------------
     * j∈[1, n-1],  |   n-1
     * j∈[2, n-1],  |   n-2
     * ...          |   ...
     * j∈[n-2, n-1],|   2
     * j∈[n-1],|    1
     * 
     * 内层循环一共执行了(n-1)+(n-2)+...+1=(n² - n)/2次，
     * 忽略低次项，忽略常数项，取最高次n²
     * 得到时间复杂度为：O(n²)
     */
    public static void selectSort(int[] array) {
        int minIndex = 0;
        for (int i = 0; i < array.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            //交换
            if (array[minIndex] < array[i]) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}

打印结果：

1 2 5 7 9 15 30