·

前言

大家還記得我?guī)讉€月前挖的一個大坑嗎？非要自不量力的來講講排序家族的故事，這不是！今天我回來繼續(xù)填這個坑，搞不好會把自己埋在這了/(ㄒoㄒ)/~~

話說關(guān)于這些排序算法的總結(jié)網(wǎng)上各種版本的都有，并且有些寫的非常詳細，如果你想對比各種算法的優(yōu)缺點、復(fù)雜度、穩(wěn)定性等等，建議你去看看那些文章，對于知識的積累還是非常有幫助的，最起碼可以應(yīng)付一些考試和面試。

今天我突然來了興致，也想來寫寫排序算法，那么我們先拿誰來開刀呢？還是選擇排序吧，誰讓它好欺負呢！當然我不想講那些專業(yè)性的東西，只是想說一下我自己的學(xué)習(xí)過程和對這個算法的理解。

選擇排序

今天我們拋開晦澀的算法定義，來重新認識一下選擇排序，想要理解選擇排序的工作原理，首先需要理解什么是選擇。那么什么是選擇呢？其實生活之中到處充滿了選擇，比如“今天上班需要穿哪件衣服？”，“中午吃飯到底是吃西紅柿炒雞蛋還是土豆牛肉呢？”等等，類似的問題還有很多，當我們回答這些問題時，都是在做出自己的選擇，而選擇排序相對于生活中的選擇問題來說，那簡直是so easy!

為了更加清晰地認識到選擇排序的本質(zhì)，我們撥開它的一層層外衣，當然了這不是在扒洋蔥，我們僅僅是挑一種適合理解的方式。假設(shè)我有五個大小不一樣的蘋果，現(xiàn)在要求你按照從小到大的順序把蘋果排成一行，為什么非得要排成一行呢？我想去串一串糖葫蘆不行嗎！行行行！既然你同意了，接下來我們看看怎么把這5個蘋果從小到大排成一行。

下面進入正題，既然要排序，第一直覺，我選擇一個最小的放在第1個位置上，然后從剩下的4個蘋果里選擇一個最小的放在第2個位置上，接著從剩下的3個蘋果里選擇一個最小的放在第3個位置上，繼續(xù)從剩下的2個蘋果里選擇一個最小的放在第1個位置上，然后從剩下的1個……——錯！錯！錯！你是不是說順嘴了，一個蘋果還選什么最小的，直接拿過來放在最后不就完成了，是不是很神奇？我做了4次選擇居然就完成了排序，是不是感覺選擇排序有點意思了。

我感覺講到這里，你大概了解了它為什么叫做選擇排序了吧？反正我的老師沒有這么給我講過，接下來我們加一個限制，假設(shè)一開始5個蘋果就放在排成一行的盤子中，首先還是選擇一個最小的，我用我敏銳的目光發(fā)現(xiàn)第3個蘋果是5個中最小的，然后怎么做？我想把它放在開頭的位置，可是那個盤子里已經(jīng)有一個蘋果了，怎么辦？我就左手拿起第1個盤子里的蘋果，右手拿起第3個盤子里的蘋果這么一交換，就實現(xiàn)了我的目的，然后從后4個盤子中選擇出最小的蘋果和第2個盤子里的蘋果交換，繼續(xù)從后3個盤子中選擇出最小的蘋果和第3個盤子里的蘋果交換，接著從后2個盤子中選擇出最小的蘋果和第4個盤子里的蘋果交換，最后一個盤子里的蘋果就不用換了，它都被換完了，肯定是最大的了……

其實在上述操作中，我們可能會遇到這種情況，比如一開始這5個蘋果放在盤子中，我發(fā)現(xiàn)第1個蘋果就是5個蘋果中最小的，那怎么辦？——我說你是不是傻了？那不正好嗎！這個蘋果還省得換了呢。其實在后面的操作中也可能遇到這種情況，我們只要注意就好。

在實際操作中我們還有一個問題需要解決，那就是在幾個蘋果中找到最小的，你說說是怎么找的？你別告訴我一眼就看出來了，那我會送一噸蘋果讓你一眼給我挑出個最小的，看看你還能不能一眼看出來！如果不是一眼看出來的，那么我們究竟是怎樣從5個蘋果中選擇出了最小的1個蘋果呢？實際上在這個過程中我們做了4次比較，首先我們會假定我們看到的第1個蘋果是最小，然后那這個蘋果依次和剩下的4個蘋果進行比較，如果發(fā)現(xiàn)在比較過程中還有更小的蘋果，那么我們會記下它的位置，接下來會拿這個更小的蘋果跟剩下的蘋果比較（也就是說，此時最小的蘋果的候選位置發(fā)生了變化），直到比較到最后一個蘋果，那么我們最后一個候選選項就是此輪比較過程的最終勝出者，其實也就是最小的。

大家可以想想是不是這么一回事，可能在數(shù)量少的時候還不明顯，但是數(shù)量一增多，你就會發(fā)現(xiàn)，你確實就是這樣找最小的蘋果，當然了在實際生活中我們可能不會按排成一行順序比較，很可能蘋果是排成一堆的，也可能亂七八糟的散落一地，但是選擇的方法還是一致的,也是有一定順序的，只是我們沒有擺的那么明顯而已，如果不是按照某個順序把所有的蘋果比較一遍，那么很抱歉，你極有可能選擇了錯誤的蘋果。

看到這里我們來總結(jié)一下我們是怎樣把5個蘋果按從小到大的順序排成一行的，總的來說我們每次都挑選剩下蘋果中最小的1個，然后依次排放，其實我們一共挑選了4次，咦？這個在程序中好像是一個循環(huán)遍歷就能實現(xiàn)，好像只需要遍歷n-1次。再來看每次挑選，我們拿著剩余的m個蘋果中的1個，然后和剩余的m-1個蘋果依次比較大小，選出此輪最小的蘋果，咦？怎么每輪挑選好像也是一個循環(huán)遍歷啊？只需要遍歷m-1次既可以了。

講到這里我們需要從蘋果的身上回到程序中來了，通過上面的分析，你發(fā)現(xiàn)的沒錯，選擇排序的主程序就是一個循環(huán)套著另一個循環(huán)，對于n個蘋果，外層循環(huán)表示一共需要挑選n-1輪最小的蘋果，對于每一輪假設(shè)沒排序的蘋果還有m個，那么我只需要拿著其中的一個和剩余的m-1個蘋果比較找到最小的就行，也就是內(nèi)層循環(huán)表示需要比較m-1次就行，然后依照思路實現(xiàn)代碼即可。

代碼實現(xiàn)

代碼君被我壓制了這么久，已經(jīng)迫不及待的想要出來和大伙見面了，下面有請代碼出場：

相信你如果理解了前面蘋果的問題，應(yīng)該很容易看懂代碼的含義，有什么不清楚的地方，也歡迎你提出自己的疑問，當然如果覺得我理解的有問題或者代碼有錯，也歡迎大家批評指正。

運行測試

選擇排序–源碼

如果你想運行測試一下，可以復(fù)制或者下載源代碼，在本機運行測試一下，當然也可以選擇在線編輯器運行查看結(jié)果，要是你想看具體的排序過程可以使用select_sort_for_explain()函數(shù)代替select_sort()函數(shù)編譯執(zhí)行，就可以看到詳細的運行結(jié)果。