選擇排序是一個非常經(jīng)典的排序算法在之前也詳細(xì)的講過了，今天單獨提出來再講一次：

插入排序算法基本思路：

遍歷輸入的整數(shù)數(shù)組中的未排序的元素，找到其中最小的值，和已經(jīng)排序被排序的元素右邊的一個元素進(jìn)行交換進(jìn)行交換。

舉個例子：

例如我們現(xiàn)在有輸入數(shù)組[4, 3, 2, 1]我們需要把他排序成[1, 2, 3, 4]，因此我們現(xiàn)在要找到輸入數(shù)組中最小的元素，也就是1，然后將它和4交換，然后找到剩下數(shù)組中最小的元素，也就是2，然后和3交換，以此類推。最后我們就會得到[1, 2, 3, 4]。

知道了基本思路，讓我們來看看他的時間復(fù)雜度和空間復(fù)雜度。

時間復(fù)雜度：

在排序第一個數(shù)的時候我們需要在數(shù)組中 0 ~ n - 1的范圍上尋找到最小值，然后和0交換。

在排序第二個數(shù)的時候我們需要在數(shù)組中 1 ~ n - 1的范圍上尋找到最小值，然后和1交換。

....

在排序第二個數(shù)的時候我們需要在數(shù)組中 n - 2 ~ n - 1的范圍上尋找到最小值，然后和n - 1交換。

因此我們不難發(fā)現(xiàn)總的時間復(fù)雜度是 ，所以很明顯這個是一個等差數(shù)列的加和，根據(jù)等差數(shù)列求和公式，我們可以得出他的時間復(fù)雜度是，因此我們?nèi)∽罡唔椌褪?img class="math-inline" src="https://math.jianshu.com/math?formula=O(n%5E2)" alt="O(n^2)" mathimg="1">。

空間復(fù)雜度：

空間復(fù)雜度是，我們只需要兩個變量來儲存交換雙方的下標(biāo)，所以我們只需要存儲額外的兩個下標(biāo)的值就行了，所以空間復(fù)雜度是。

接下來我們來看代碼:

public class Code01_SelectionSort {

    public static void selection(int[] arr){
        // 輸入整數(shù)類型的列表
        if(arr == null || arr.length < 2){
            // 如果輸入的數(shù)組為空或者小于 2就直接返回，為空和為1都不用排序是吧？
            return;
        }

        for(int i = 0; i < arr.length; i++) {
            //遍歷數(shù)組中的每一個元素，申請一個變量記錄最小的元素
            int minIdx = i;
            for(int j = i + 1; j < arr.length; j++){
                // 找到最小元素，交換
                minIdx = arr[i] < arr[minIdx] ? j : minIdx;
            }
            swap(arr, minIdx, i);
        }
    }

    public static void swap(int[] arr, int idxOne, int idxTwo){
        // 交換兩個元素
        int temp = arr[idxOne];
        arr[idxOne] = arr[idxTwo];
        arr[idxTwo] = temp;
    }
}

Reference： https://italk.mashibing.com/course/detail/cour_00004003