前言

前面幾篇分享了插入排序和交換排序，接下來說說選擇排序~~~

選擇排序（Selection sort）：每一趟在待排序元素中選取元素值最小(或最大)的元素加入有序子序列。即在一堆數(shù)據(jù)中，每次挑出最小的或最大的放入其他有序序列中，當(dāng)選擇完所有待排序數(shù)據(jù)時(shí)，排序就完成了。

選擇排序有兩種：簡(jiǎn)單選擇排序和堆排序；接下來就從簡(jiǎn)單的開始，先來說說簡(jiǎn)單選擇排序。

正文

1.1 簡(jiǎn)單選擇排序算法思想

簡(jiǎn)單選擇排序很直觀，直接從待排序列表中找出最?。ɑ蜃畲螅┑脑胤诺接行蛐蛄兄校钡酱判蛄斜碇械脑乇贿x擇完為止。

算法思想

• 在待排序列表中找出最?。ɑ蜃畲螅┑脑?；

• 將找出的元素放到有序序列中；

• 重復(fù)以上步驟，直到待排序列表中元素被選擇完為止。

1.2簡(jiǎn)單選擇排序算法實(shí)現(xiàn)與解析

• 算法實(shí)現(xiàn)

  image-20210509173951127

• 運(yùn)行效果

  image-20210509174139509

• 步驟解析(升序)：

  image-20210510001331070

  上圖步驟說明：

  圖中黃色方塊是標(biāo)記最小元素的位置，紅色方塊是代表待排序列表中下一個(gè)要比較的元素，綠色方塊代表有序序列，剛開始有序序列中可以認(rèn)為沒有元素。上述案例演示中共六個(gè)元素，需要進(jìn)行五趟（n-1）排序，如下：

  第一趟排序

  第1.1步，此時(shí)有序序列中認(rèn)為沒有元素，標(biāo)記0索引位為最小元素位置，開始依次比較待排序列表中后面的每一個(gè)元素，先比較元素5， 5大于2，最小元素標(biāo)記位不變，繼續(xù)比較；

  第1.2步，接著用標(biāo)記的最小位元素2與元素6比較，6大于2，最小元素標(biāo)記位不變，繼續(xù)比較；

  第1.3步，接著用標(biāo)記的最小位元素2與元素1比較，1小于2，需要改變最小元素標(biāo)記位，此時(shí)最小元素的標(biāo)記位為1的索引位，即min為3，然后繼續(xù)比較；

  第1.4步，接著用標(biāo)記的最小位元素1與元素9比較，9大于1，最小元素標(biāo)記位不變，繼續(xù)比較；

  第1.5步，接著用標(biāo)記的最小位元素1與元素3比較，3大于1，最小元素標(biāo)記位不變，繼續(xù)比較；

  第1.6步，待排序列表遍歷完成，找到最小元素索引位為3，即元素1，則需要把元素1放到有序序列中，這里就直接放在待排序列表前面，只需將第一個(gè)元素和得到的最小元素交換位置即可，此時(shí)有序序列中的元素有一個(gè)1；

  第二趟排序

  經(jīng)過第一趟排序，有序序列中有一個(gè)元素，即當(dāng)前整個(gè)數(shù)組的第一個(gè)元素(綠色方塊)；接下來繼續(xù)在待排序列表中找最小的元素加入到序列中。

  第2.1步，第二趟剛開始標(biāo)記1索引位為最小元素位置，然后依次比較后面的每一個(gè)元素，先比較元素6，6大于5，最小標(biāo)記位不變，繼續(xù)比較；

  第2.2步，接著用標(biāo)記的最小位元素5與元素2比較，2小于5，需要改變最小元素標(biāo)記位，此時(shí)最小元素的標(biāo)記位為2的索引位，即min為3，然后繼續(xù)比較；

  第2.3步，接著用標(biāo)記的最小位元素2與元素9比較，9大于2，最小元素標(biāo)記位不變，繼續(xù)比較；

  第2.4步，接著用標(biāo)記的最小位元素2與元素3比較，3大于2，最小元素標(biāo)記位不變，繼續(xù)比較；

  第2.5步，待排序列表遍歷完成，找到最小元素索引位為3，即元素2，則需要把元素2加入到有序序列中，這里還是接著上一趟排序得到有序序列往后放，只需將第二個(gè)元素5和得到的最小元素2交換位置即可，此時(shí)有序序列中的元素有兩個(gè)（即1,2）；

  第三趟、第四趟、第五趟就不詳細(xì)寫步驟啦，重復(fù)上面步驟即可，直到待排序列表中的元素被選擇完為止，這樣就得到最終的排序結(jié)果啦。

1.3 簡(jiǎn)單選擇排序算法分析

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

  不管待排序列表是有序、逆序還是亂序，如果待排序列表中如果有個(gè)n個(gè)元素，就得需要n-1趟處理才能得到最終的結(jié)果，則在其中比較大小的次數(shù)為：(n-1)+(n-2)+(n-3)+...+1，而對(duì)于其中交換元素的次數(shù)小于n-1次，則根據(jù)時(shí)間復(fù)雜度表示形式，去除常數(shù)和系數(shù)，取高階進(jìn)行表示，則簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n²)。

• 空間復(fù)雜度

  在核心排序過程中只采用了固定的幾個(gè)中間變量(min,i,j,temp)，則空間復(fù)雜度為O(1)。

• 穩(wěn)定性

  在選擇排序過程中，兩個(gè)元素相等，但還是有可能交換位置，則簡(jiǎn)單排序算法不穩(wěn)定，如下：

  image-20210510224042084

  在上圖中，黃色方塊2會(huì)先標(biāo)記為最小位，依次往后進(jìn)行比較找到真實(shí)的最小位的元素為白色方塊1，則需要將白色方塊1放到前面有序序列中，其實(shí)就是和黃色方塊2進(jìn)行位置交換，這樣最終就會(huì)導(dǎo)致原來兩個(gè)相等元素2的順序發(fā)生改變，則簡(jiǎn)單選擇排序?yàn)椴环€(wěn)定算法。

綜上所述，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n²)，空間復(fù)雜度為O(1)，是不穩(wěn)定算法。

總結(jié)

看完簡(jiǎn)單選擇排序，小伙伴會(huì)覺得和直接插入排序很像，但是他們有一個(gè)很大區(qū)別，簡(jiǎn)單選擇排序是將已經(jīng)得到的最小(或最大)元素依次放入到有序序列中，而直接插入排序是在從待排序列表中直接取出一個(gè)元素，然后在和原來有序列表中元素進(jìn)行比較，找到對(duì)應(yīng)位置，然后插入到對(duì)應(yīng)位置。

對(duì)比以往排序算法的經(jīng)驗(yàn)，簡(jiǎn)單選擇排序算法的元素比較次數(shù)還是可以優(yōu)化的，所以下一次來說說比較難搞的堆排序。

一個(gè)被程序搞丑的帥小伙，關(guān)注"Code綜藝圈"，跟我一起學(xué)~~~