開篇
上篇我們好好聊了聊冒泡排序，這篇我們來聊聊另一種初級排序算法——選擇排序
正文
選擇排序的算法思路同樣很簡單。還是數(shù)組為例，我們現(xiàn)在有個整數(shù)數(shù)組，要求將其中整數(shù)元素按值的大小從小到大排個序。選擇排序的具體思路是這樣：先從頭遍歷數(shù)組，找出其中值最小的那個元素，然后將其值同遍歷區(qū)間最開始那個元素交換，如果值最小的元素恰是最開始那個元素，就自己跟自己交換值。第一遍遍歷完成，數(shù)組中最小的值已經(jīng)是數(shù)組第一個元素，此時數(shù)組第一個元素已部分有序，將重新遍歷的初始下標(biāo)加一，開始下次遍歷，如此循環(huán)，直至遍歷區(qū)間內(nèi)只剩一個元素，此時數(shù)組已整體有序。
來具象化捋一遍選擇排序的邏輯：
``
/*
設(shè)現(xiàn)有無序數(shù)組 a = [40, 50, 20, 30, 10]
其有序狀態(tài)應(yīng)為 a = [10, 20, 30, 40, 50]
我們對其做下選擇排序，具象展示如下：
數(shù)組下標(biāo)：a[0] a[1] a[2] a[3] a[4]
初始值： 40 50 20 30 10
第一次選擇遍歷過程： 40 50 20 30 10 (遍歷區(qū)間值最小元素為a[4],
↑ ↑ 與遍歷區(qū)間初始下標(biāo)a[0]交換值)
第二次選擇遍歷過程： 10 50 20 30 40 (最小元素為a[2],與a[1]交換值，
--- ↑ ↑ 下劃線標(biāo)示的元素已部分有序)
第三次選擇遍歷過程： 10 20 50 30 40 (最小元素為a[3],與a[2]交換值，
---------- ↑ ↑ 下劃線標(biāo)示的元素已部分有序)
第四次選擇遍歷過程： 10 20 30 50 40 (最小元素為a[4],與a[3]交換值，
------------------ ↑ ↑ 下劃線標(biāo)示的元素已部分有序)
第五次選擇遍歷過程： 10 20 30 40 50 (遍歷區(qū)間內(nèi)只剩一個元素了，
------------------------- ↑↑ 表明此時數(shù)組已整體有序)
數(shù)組此時已整體有序： 10 20 30 40 50 (數(shù)組此時已整體有序）
--------------------------------
*/
OK 邏輯捋的差不多了我們開始擼代碼，以 Java 為例，我們先來擼個為整數(shù)數(shù)組選擇排序的遞歸實現(xiàn)版本：
/**
* @see: 選擇排序的遞歸實現(xiàn)
* @param array: 待排序數(shù)組，我們采用原地排序
* @param start: 當(dāng)次查找最小值（遍歷區(qū)間）的初始下標(biāo)，初次調(diào)用值應(yīng)為0
*/
public static void sortSelect(int[] array, int start){
//遞歸結(jié)束條件，此時數(shù)組已整體有序
if (start >= array.length - 1){
return;
}
//先假定遍歷區(qū)間第一個下標(biāo)的值為最小值;
int minValueIndex = start;
//開始遍歷特定數(shù)組區(qū)間，將區(qū)間內(nèi)最小值交換到區(qū)間初始位置
for (int i = start + 1; i <= array.length - 1; i ++){
if (array[i] < array[minValueIndex]){
minValueIndex = i;
}
}
//把最小的值交換到遍歷區(qū)間初始下標(biāo)位置
int mid = array[start];
array[start] = array[minValueIndex];
array[minValueIndex] = mid;
//遞歸開始遍歷下個遍歷區(qū)間
sortSelect(array, start + 1);
}
我們在實際生產(chǎn)環(huán)境中寫排序算法肯定不能用遞歸，在 Java 中遞歸的函數(shù)調(diào)用棧太深會致開銷甚大，上面主要是為便于理解來的初級版本，我們來優(yōu)化成非遞歸版本，即雙層嵌套版本：
/**
* @see: 選擇排序的非遞歸實現(xiàn)，即雙層嵌套實現(xiàn)
* @param array: 待排序數(shù)組，我們采用原地排序
*/
public static void sortSelect(int[] array){
//遞歸結(jié)束條件，此時數(shù)組已整體有序
for (int start = 0; start < array.length - 1; start ++){
//先假定遍歷區(qū)間第一個下標(biāo)的值為最小值;
int minValueIndex = start;
for (int startInner = start + 1; startInner <= array.length - 1; startInner ++ ){
if (array[startInner] < array[minValueIndex]){
minValueIndex = startInner;
}
}
//把最小的值交換到遍歷區(qū)間初始下標(biāo)位置
int mid = array[start];
array[start] = array[minValueIndex];
array[minValueIndex] = mid;
//循環(huán)開始遍歷下個遍歷區(qū)間
}
}
兩種實現(xiàn)代碼擼下來，相信你已徹底掌握了選擇排序算法。
尾巴
選擇排序有兩個特點：
- 運行時間和輸入無關(guān)，其時間復(fù)雜度恒為 О(n2)，即使你輸入的數(shù)組本來就整體有序也是如此！
- 數(shù)據(jù)值交換（或言數(shù)據(jù)移動）是最少的，如上所示，一次遍歷只有一次值交換，還有可能是自己跟自己交換，對比冒泡排序，你知道我在說什么！
選擇排序需要的額外空間復(fù)雜度同冒泡排序，為О(1)
讀者請自行發(fā)散思維把以上代碼改成為 Comparable 數(shù)組排序的版本。
下篇我們聊插入排序。
完。
