選擇排序（Selection sort）是一種不穩(wěn)定的排序方法棋嘲，每一趟從待排序的數(shù)據(jù)元素中選出最熊А（或最大）的一個(gè)元素堤魁，順序放在已排好序的數(shù)列的最后蜜暑，直到全部待排序的數(shù)據(jù)元素排完铐姚。其主要應(yīng)用于計(jì)算機(jī)和數(shù)學(xué)領(lǐng)域。它的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)肛捍。如果某個(gè)元素位于正確的最終位置上隐绵，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素拙毫，它們當(dāng)中至少有一個(gè)將被移到其最終位置上依许，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中缀蹄，選擇排序?qū)儆诜浅：玫囊环N峭跳。
為什么說選擇排序是一種不穩(wěn)定的排序方法呢膘婶？舉個(gè)例子，序列58529蛀醉，我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換悬襟，變成了28559 ，那么原序列中兩個(gè)5的相對(duì)前后順序就被破壞了拯刁，所以選擇排序是一個(gè)不穩(wěn)定的排序算法古胆。
選擇排序的基本方法是：
通過n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄筛璧，并和第i（1<=i<=n）個(gè)記錄進(jìn)行交換逸绎。當(dāng)i=n時(shí)，所有記錄有序排列夭谤。
排序?qū)嵗?/p>
初始關(guān)鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序結(jié)果 13 27 38 49 49 65 76 97
void select_sort(int *a, int n)
{
? ? ? ? ? register int i, j, min, t;
? ? ? ? ?for( i =0; i < n -1; i ++)
? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? min = i; //查找最小值
? ? ? ? ? ? ? ? ? ? for( j = i +1; j < n; j ++)
? ? ? ? ? ? ? ? ? ? ? ? if( a[min] > a[j])
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? min = j; //交換
? ? ? ? ? ? ? ? ? if(min != i)
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? t = a[min]; a[min] = a[i]; a[i] = t;
? ? ? ? ? ? ? ? ? }
? ? ? ? }
}
