「 選擇排序 」雖然在實際應(yīng)用中沒有「 插入排序 」廣泛，但它也是我們學(xué)習(xí)排序算法中必不可少的一種。「 冒泡排序 」和「 插入排序 」都是在兩層嵌套循環(huán)中慢慢比較元素，不停的調(diào)整元素的位置。而「 選擇排序 」就比較直接了，屬于不出手則已，一出手，相應(yīng)的元素就必須要到位，元素的位置就不會再變了。

[[320109]]

下面我們來詳細了解下一下它的邏輯。

一、「 選擇排序 」是什么?

選擇排序 也是一種很簡單的排序算法，它的思路也是將一組待排序的數(shù)據(jù)，分成2段，一段是“已排序”了的數(shù)據(jù)，另一段是“未排序”的數(shù)據(jù)。當(dāng)然，在最開始的時候，“已排序”區(qū)段里是沒有數(shù)據(jù)的。排序開始后，每次都從“未排序”的數(shù)據(jù)中取出一個最小的元素(注意，這里是取最小的元素，這一點與「 插入排序 」是不同的)，然后將這個最小的元素插入到“已排序”數(shù)據(jù)中末尾元素的后面(這里其實是將這個最小元素與“已排序”數(shù)據(jù)的末尾緊鄰的下一位元素進行交換)，這樣保持了“已排序”中的數(shù)據(jù)永遠是有序的。一直這么循環(huán)的去處理，直到所有的“未排序”的數(shù)據(jù)都已交換完，則整個排序全部完成。

下面用圖示例講解一下：

(圖片來源網(wǎng)絡(luò))

從上圖可以看到，初始數(shù)組是

要對這個數(shù)組進行從小到大排序，默認初始狀態(tài)是全部無序的，因此對這個數(shù)組開始遍歷找最小元素。

1.第一遍大循環(huán)時，在整個數(shù)組中找到最小元素“13”，將這個最小元素“13”與數(shù)組的開頭位置元素“29”進行交換。交換后數(shù)組為：

2.第二遍大循環(huán)時，元素“13”屬于“已排序”區(qū)段了，剩下所有元素都屬于“未排序”的區(qū)段。從剩下元素中找到最小元素“29”，將這個最小元素“29”與元素“72”進行交換(因為元素“72”是已排序數(shù)組緊鄰的后一位元素)，交換后數(shù)組為：

3.第三遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“36”，將這個最小元素“36”與元素“98”進行交換(因為元素“98”是已排序數(shù)組緊鄰的后一位元素)，交換后數(shù)組為：

4.第四遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“51”，將這個最小元素“51”與元素“72”進行交換(因為元素“72”是已排序數(shù)組緊鄰的后一位元素)，交換后數(shù)組為：

5.第五遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”、“51”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“52”，將這個最小元素“52”與元素“87”進行交換(因為元素“87”是已排序數(shù)組緊鄰的后一位元素)，交換后數(shù)組為：

6.第六遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”、“51”、“52”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“66”，發(fā)現(xiàn)這個最小元素“66”已經(jīng)是位于已排序數(shù)組緊鄰的后一位元素了，因此無需交換，數(shù)組保持不變：

7.第七遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”、“51”、“52”、“66”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“72”，將這個最小元素“72”與元素“87”進行交換(因為元素“87”是已排序數(shù)組緊鄰的后一位元素)，交換后數(shù)組為：

8.第八遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”了，剩下其它元素都屬于“未排序”的。從剩下元素中找到最小元素“87”，發(fā)現(xiàn)這個最小元素“87”已經(jīng)是位于已排序數(shù)組緊鄰的后一位元素了，因此無需交換，數(shù)組保持不變：

9.第九遍大循環(huán)時，“已排序”區(qū)段里已經(jīng)有元素“13”、“29”、“36”、“51”、“52”、“66”、“72”、“87”了，剩下未排序的元素只有“98”這一個了,直接保持其位置不變即可，即，此時全部排序完成，數(shù)組最終狀態(tài)為：

下面我們來看一個選擇排序的代碼示意：

算法題：對數(shù)組arr進行從小到大的排序，假設(shè)數(shù)組arr不為空，arr的長度為n思路：采用選擇排序方法

public void selectionSort(int[] arr){ 
    int i,j; 
    int n = arr.length; 
     
    //每一次大循環(huán)都能找出剩余元素的最小值 
    for(i=0; i<n; i++){ 
        //min變量是用于存放最小值的下標(biāo)的，在剛開始的時候，假設(shè)位置i是最小值，初始時將i賦值給min 
        int min = i; 
        //子循環(huán)是用于比較大小，從i的后面一位開始遍歷，遍歷后面所有元素 
        for(j=i+1; j<n; j++){ 
            //如果有元素小于min位的值，則將此元素的下標(biāo)賦值給min 
            if(arr[j] < arr[min]){ 
                min = j; 
            } 
        } 
        //如果min不等于i，說明剛在在子循環(huán)里，找到了最小值，則需要交換元素位置 
        if(min!=i){ 
            //swap方法是用于交換數(shù)組中2個位置的值（傳入數(shù)組、下標(biāo)），swap方法省略不寫了。 
            swap(arr,min,i); 
        } 
    } 
} 

二、「 選擇排序 」的性能怎么樣?

我們按照之前文章中講到的排序算法評估方法來對「 選擇排序 」進行一下性能評估：

• 時間復(fù)雜度：

選擇排序原理就是在兩層嵌套循環(huán)里進行對比和交換，所以簡單來講，其一般情況下的時間復(fù)雜度就是O(n*n)了。但如果仔細去分析的話，就得看具體的數(shù)據(jù)情況。但無論數(shù)據(jù)情況是怎樣的，其元素比較的次數(shù)是一樣的，因此無論是最好情況還是最壞情況，它的元素比較次數(shù)沒區(qū)別。那再看看元素交換次數(shù)，如果待排序的數(shù)據(jù)本身就是有序的，其根本不需要交換元素，交換次數(shù)為0，但如果待排序的數(shù)據(jù)全部都是逆序的，那需要做n-1次元素交換。

因此，其選擇排序的最好、最壞、平均情況下，其時間復(fù)雜度都是：O(n*n)。

• 空間復(fù)雜度：

選擇排序完全就是比較和交換數(shù)據(jù)，只需要一個輔助空間用來存儲待比較的元素的小標(biāo)，并沒有消耗更多的額外空間，因此其空間復(fù)雜度是O(1)。

• 排序穩(wěn)定性：

選擇排序算法不是穩(wěn)定性排序算法。這里再解釋一下穩(wěn)定性排序是指：2個相等的元素，在排序前的相對前后位置和排序完成后的，相對前后位置保持一致。

選擇排序為啥不是穩(wěn)定性排序呢，舉個例子：數(shù)組 6、7、6、2、8，在對其進行第一遍循環(huán)的時候，會將第一個位置的6與后面的2進行交換。此時，就已經(jīng)將兩個6的相對前后位置改變了。因此選擇排序不是穩(wěn)定性排序算法。

• 算法復(fù)雜性：

選擇排序的算法無論是其設(shè)計思路上，還是代碼的編寫上都不復(fù)雜，其算法復(fù)雜性是較為簡單的。

以上，就是對數(shù)據(jù)結(jié)構(gòu)中「 選擇排序 」的一些思考，您有什么疑問嗎?

碼字不易啊，喜歡的話不妨轉(zhuǎn)發(fā)朋友，或點擊文章右下角的“在看”吧。😊