上一小節(jié)給大家介紹了桶排序，最大的缺點(diǎn)就是耗費(fèi)內(nèi)存，如果需要排序的數(shù)的范圍是int，那我們要定義一個大小為21474836478的數(shù)組嗎，或是如果有浮點(diǎn)數(shù)(小數(shù))的出現(xiàn)，顯然桶排序并不適用，今天要給大家的介紹的是另外一種排序方法，沒錯，就是選擇排序。
選擇排序是一種簡單直觀的排序算法，它的工作原理是每一次從待排序的數(shù)列元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
在本文里，我們只介紹從小到大排序。
舉一個小例子：
最后我們一起來看一下c++代碼的實(shí)現(xiàn)
從代碼中不難看出選擇排序的時間復(fù)雜度是O(n^2)。如果對于復(fù)雜度還不是很懂的話，可以瀏覽一下 復(fù)雜度 。
缺點(diǎn)
選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。
下一節(jié)，會給大家介紹時間復(fù)雜度同樣是O(n^2)，但更穩(wěn)定的冒泡排序。
