選擇排序法:科學運算方法-中文百科頻道

基本思想

排序定義。所謂計算機中的排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。而排序算法（Sorting algorithm）則是一種能将一串數據依照特定的方式進行排列的一種算法。n排序方式。利用所需重排記錄的排序碼（Sort Key）的值的大小，按照升序或降序将原紀錄的順序重新安排。排序類别。内排序可以分為插入排序（insertion sort）、選擇排序（selection sort）、交換排序（exchange sort）、歸并排序（merge sort）以及分配排序（distribution sort）。n選擇排序法是在要排序的一組數中，選出最小（或最大）的一個數與第一個位置的數交換；在剩下的數當中找最小的與第二個位置的數交換，即順序放在已排好序的數列的最後，如此循環，直到全部數據元素排完為止。

算法描述

選擇排序法的第一層循環從起始元素開始選到倒數第二個元素，主要是在每次進入的第二層循環之前，将外層循環的下标賦值給臨時變量，接下來的第二層循環中，如果發現有比這個最小位置處的元素更小的元素，則将那個更小的元素的下标賦給臨時變量，最後，在二層循環退出後，如果臨時變量改變，則說明，有比當前外層循環位置更小的元素，需要将這兩個元素交換。

簡單選擇排序算法分析：在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀态就已經是正序排列了，則不需要移動記錄。最壞情況下，即待排序記錄初始狀态是按逆序排列的，則需要移動記錄的次數最多為3（n-1）。簡單選擇排序過程中需要進行的比較次數與初始狀态下待排序的記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即進行比較操作的時間複雜度為O(n2)。

選擇排序法是對定位比較交換法（也就是冒泡排序法）的一種改進。在講選擇排序法之前我們先來了解一下定位比較交換法。為了便于理解，設有10個數分别存在數組元素a～a中。定位比較交換法是由大到小依次定位a～a中恰當的值（和武林大會中的比武差不多），a中放的自然是最小的數。如定位a,先假定a中當前值是最大數，a與後面的元素一一比較，如果a更大，則将a、a交換，a已更新再與後面的a～a比較，如果a還要大，則将a、a交換，a又是新數，再與a比較。一輪比完以後，a就是最大的數了，本次比武的武狀元誕生了，接下來從a開始，因為狀元要休息了，再來一輪a就是次大的數，也就是榜眼，然後從a開始，比出探花，真成比武大會了，當比到a以後，排序就完成了。

穩定性

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為隻剩下它一個最大的元素了。那麼，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。