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

[[320109]]

下面我們來(lái)詳細(xì)了解下一下它的邏輯。

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

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

下面用圖示例講解一下：

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

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

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

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

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

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

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

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

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

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

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

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

下面我們來(lái)看一個(gè)選擇排序的代碼示意：

算法題：對(duì)數(shù)組arr進(jìn)行從小到大的排序，假設(shè)數(shù)組arr不為空，arr的長(zhǎng)度為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í)候，假設(shè)位置i是最小值，初始時(shí)將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，說(shuō)明剛在在子循環(huán)里，找到了最小值，則需要交換元素位置 
        if(min!=i){ 
            //swap方法是用于交換數(shù)組中2個(gè)位置的值（傳入數(shù)組、下標(biāo)），swap方法省略不寫了。 
            swap(arr,min,i); 
        } 
    } 
} 

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

我們按照之前文章中講到的排序算法評(píng)估方法來(lái)對(duì)「 選擇排序 」進(jìn)行一下性能評(píng)估：

• 時(shí)間復(fù)雜度：

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

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

• 空間復(fù)雜度：

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

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

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

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

• 算法復(fù)雜性：

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

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

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