本文著重講解選擇排序:
原理:每一趟從待排序的記錄中選出最小的元素,順序放在已排好序的序列最後,直到全部記錄排序完畢。
舉例:
數組
如圖,是五個無序的數據。接下來就需要使用選擇排序將其進行排序。
思路:
先默認選定一個數據,認為是最小的。讓其與後面的所有數據進行比較,如發現比自己更小的則交換位置,當本輪比較完成以後,前面的數據則變成最小的。
五個數據 默認比較四輪 就可以確定所有數據的順序
演示過程:
第一輪比較:
默認選定下標為0的位置上的數據為最小的。讓他與後面所有數據進行比較
紅色部分為第一輪
比較的位置為:
0-1 0-2 0-3 0-4
交換了下標為0和下標為1 的數據 ,發現2是在此數組中最小的數據,此時已經確定了下標為0的數據。 結 果為: 2,9,5,4,7
第二輪比較:
第二輪中我們可以選擇下標為1 的位置默認為本輪最小數據,依次與後面數據進行對比。
藍色部分為第二輪
比較位置:
1-2 1-3 1-4
交換了下標為1和2 ,結果為 2,5,9,4,7
然後繼續進行對比,又交換了下標為1和下標為3 結果為: 2,4,9,5,7
第三輪比較:
第三輪比較中默認把下標為2 最為最小值,依次跟後面數據進行比較
綠色部分為第三輪
比較位置:
2-3 2-4
第三輪中 交換了 下標為2和3 結果為:2,4,5,9,7
第四輪:
默認選定下標為3的位置上的數據為最小的。讓他與後面所有數據進行比較
橙色部分為第四輪
比較位置:
3-4
比較了一次,交換了下標3和4位置上的數據,結果為: 2,4,5,7,9
至此:我們將這個無序數組變得有序。
總結規律:
1 五個數據比較四輪。比較輪數為 數組.Length-1
2 默認選擇一個位置跟後面所有數據進行比較,所以每輪比較次數為
第一輪: 4次
第二輪: 3次
第三輪: 2次
第四輪: 1次
3 比較過程中發現後面數據比自己小的時候,進行數據交換
以上三條規律 則可以幫助我們來實現代碼的推導:
選擇排序代碼
至此為止,選擇排序就已經實現了。
但是我們對於代碼的效率的追求是無止境的。仔細觀察會發現,在每輪比較中,都有可能交換多次數據。比如 第二輪中 ,先交換了 1 和 2的數據,然後又交換了 1和3的數據。這是因為2上面的數據雖然比1 小,但是 並不是後面最小的數據,3此時最小的。這樣我們就涉及到 多次交換數據。為了提高執行效率,可以先當比較1和2的時候發現2是比1小,則默認把當前最小的數據變成2,讓2與後面的3比較,如果發現3比2小,則 默認當前最小的數據為3 以此類推,當把所有數據 進行比較後會得到最小的數據。然後在進行交換數據。這樣我們就看可以將交換數據的次數控制在 小於等於比較輪數的範圍內。進而提高執行效率。
代碼如下:
優化後的選擇排序
至此,優化後的代碼實現。