來自：不止思考
上一篇文章咱們已經聊過「 冒泡排序 」和「 插入排序 」了，今天我們來看一看「 選擇排序 」。「 選擇排序 」雖然在實際應用中沒有「 插入排序 」廣泛，但它也是我們學習排序算法中必不可少的一種。「 冒泡排序 」和「 插入排序 」都是在兩層嵌套循環中慢慢比較元素，不停的調整元素的位置。而「 選擇排序 」就比較直接了，屬于不出手則已，一出手，相應的元素就必須要到位，元素的位置就不會再變了。
下面我們來詳細了解下一下它的邏輯。
一、「 選擇排序 」是什麼？
選擇排序 也是一種很簡單的排序算法，它的思路也是将一組待排序的資料，分成2段，一段是“已排序”了的資料，另一段是“未排序”的資料。當然，在最開始的時候，“已排序”區段裡是沒有資料的。排序開始後，每次都從“未排序”的資料中取出一個最小的元素(注意，這裡是取最小的元素，這一點與「 插入排序 」是不同的)，然後将這個最小的元素插入到“已排序”資料中末尾元素的後面(這裡其實是将這個最小元素與“已排序”資料的末尾緊鄰的下一位元素進行交換)，這樣保持了“已排序”中的資料永遠是有序的。一直這麼循環的去處理，直到所有的“未排序”的資料都已交換完，則整個排序全部完成。
下面用圖示例講解一下：
(圖檔來源網絡)
從上圖可以看到，初始數組是
| 元素 | 29 | 72 | 98 | 13 | 87 | 66 | 52 | 51 | 36 |
|---|---|---|---|---|---|---|---|---|---|
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
要對這個數組進行從小到大排序，預設初始狀态是全部無序的，是以對這個數組開始周遊找最小元素。
- 第一遍大循環時，在整個數組中找到最小元素“13”，将這個最小元素“13”與數組的開頭位置元素“29”進行交換。交換後數組為：
元素 13 72 98 29 87 66 52 51 36 下标 1 2 3 4 5 6 7 8 - 第二遍大循環時，元素“13”屬于“已排序”區段了，剩下所有元素都屬于“未排序”的區段。從剩下元素中找到最小元素“29”，将這個最小元素“29”與元素“72”進行交換(因為元素“72”是已排序數組緊鄰的後一位元素)，交換後數組為：
元素 13 29 98 72 87 66 52 51 36 下标 1 2 3 4 5 6 7 8 - 第三遍大循環時，“已排序”區段裡已經有元素“13”、“29”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“36”，将這個最小元素“36”與元素“98”進行交換(因為元素“98”是已排序數組緊鄰的後一位元素)，交換後數組為：
元素 13 29 36 72 87 66 52 51 98 下标 1 2 3 4 5 6 7 8 - 第四遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“51”，将這個最小元素“51”與元素“72”進行交換(因為元素“72”是已排序數組緊鄰的後一位元素)，交換後數組為：
元素 13 29 36 51 87 66 52 72 98 下标 1 2 3 4 5 6 7 8 - 第五遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”、“51”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“52”，将這個最小元素“52”與元素“87”進行交換(因為元素“87”是已排序數組緊鄰的後一位元素)，交換後數組為：
元素 13 29 36 51 52 66 87 72 98 下标 1 2 3 4 5 6 7 8 - 第六遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”、“51”、“52”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“66”，發現這個最小元素“66”已經是位于已排序數組緊鄰的後一位元素了，是以無需交換，數組保持不變：
元素 13 29 36 51 52 66 87 72 98 下标 1 2 3 4 5 6 7 8 - 第七遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”、“51”、“52”、“66”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“72”，将這個最小元素“72”與元素“87”進行交換(因為元素“87”是已排序數組緊鄰的後一位元素)，交換後數組為：
元素 13 29 36 51 52 66 72 87 98 下标 1 2 3 4 5 6 7 8 - 第八遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“87”，發現這個最小元素“87”已經是位于已排序數組緊鄰的後一位元素了，是以無需交換，數組保持不變：
元素 13 29 36 51 52 66 72 87 98 下标 1 2 3 4 5 6 7 8 - 第九遍大循環時，“已排序”區段裡已經有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”、“87”了，剩下未排序的元素隻有“98”這一個了,直接保持其位置不變即可，即，此時全部排序完成，數組最終狀态為：
元素 13 29 36 51 52 66 72 87 98 下标 1 2 3 4 5 6 7 8
下面我們來看一個選擇排序的代碼示意：
算法題：對數組arr進行從小到大的排序，假設數組arr不為空，arr的長度為n思路：采用選擇排序方法public void selectionSort(int[] arr){ int i,j; int n = arr.length; //每一次大循環都能找出剩餘元素的最小值 for(i=0; i //min變量是用于存放最小值的下标的，在剛開始的時候，假設位置i是最小值，初始時将i指派給min int min = i; //子循環是用于比較大小，從i的後面一位開始周遊，周遊後面所有元素 for(j=i+1; j //如果有元素小于min位的值，則将此元素的下标指派給min if(arr[j] < arr[min]){ min = j; } } //如果min不等于i，說明剛在在子循環裡，找到了最小值，則需要交換元素位置 if(min!=i){ //swap方法是用于交換數組中2個位置的值(傳入數組、下标)，swap方法省略不寫了。 swap(arr,min,i); } }}
二、「 選擇排序 」的性能怎麼樣？
我們按照之前文章中講到的排序算法評估方法來對「 選擇排序 」進行一下性能評估：
-
時間複雜度：
選擇排序原理就是在兩層嵌套循環裡進行對比和交換，是以簡單來講，其一般情況下的時間複雜度就是O(n*n)了。但如果仔細去分析的話，就得看具體的資料情況。但無論資料情況是怎樣的，其元素比較的次數是一樣的，是以無論是最好情況還是最壞情況，它的元素比較次數沒差別。那再看看元素交換次數，如果待排序的資料本身就是有序的，其根本不需要交換元素，交換次數為0，但如果待排序的資料全部都是逆序的，那需要做n-1次元素交換。
是以，其選擇排序的最好、最壞、平均情況下，其時間複雜度都是：O(n*n)。
-
空間複雜度：
選擇排序完全就是比較和交換資料，隻需要一個輔助空間用來存儲待比較的元素的小标，并沒有消耗更多的額外空間，是以其空間複雜度是O(1)。
-
排序穩定性：
選擇排序算法不是穩定性排序算法。這裡再解釋一下穩定性排序是指：2個相等的元素，在排序前的相對前後位置和排序完成後的，相對前後位置保持一緻。
選擇排序為啥不是穩定性排序呢，舉個例子：數組 6、7、6、2、8，在對其進行第一遍循環的時候，會将第一個位置的6與後面的2進行交換。此時，就已經将兩個6的相對前後位置改變了。是以選擇排序不是穩定性排序算法。
-
算法複雜性：
選擇排序的算法無論是其設計思路上，還是代碼的編寫上都不複雜，其算法複雜性是較為簡單的。
以上，就是對資料結構中「 選擇排序 」的一些思考，您有什麼疑問嗎？
長按訂閱更多精彩▼
選擇排序穩定嗎_算法一看就懂之 選擇排序 如有收獲，點個在看，誠摯感謝
選擇排序穩定嗎_算法一看就懂之 選擇排序