選擇排序(Selection Sort)的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。

本節(jié)介紹第一種選擇排序：直接選擇排序。

直接選擇排序的基本思想

n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果：

• 初始狀態(tài)：無(wú)序區(qū)為 R[1..n]，有序區(qū)為空。
• 第 1 趟排序：在無(wú)序區(qū) R[1..n]中選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第 1 個(gè)記錄 R[1]交換，使 R[1..i]和 R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加 1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無(wú)序區(qū)。 ……
• 第 i 趟排序：第i趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為 R[1..i-1]和 R[i..n][1≤i≤n-1]。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第 i 個(gè)記錄 R[i]交換，使 R[1..i]和 R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加 1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無(wú)序區(qū)。

這樣，n 個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò) n-1 趟直接選擇排序得到有序結(jié)果。

直接選擇排序的過(guò)程

直接選擇排序的過(guò)程【參見(jiàn)動(dòng)畫(huà)演示】

算法描述

直接選擇排序的具體算法如下：

void SelectSort(SeqList R)  
{  
  int i，j，k；  
  for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)  
    k=i；  
    for(j=i+1;j<=n;j++) //在當(dāng)前無(wú)序區(qū)R[i..n]中選key最小的記錄R[k]  
      if(R[j].key<R[k].key)  
        k=j; //k記下目前找到的最小關(guān)鍵字所在的位置  
      if(k!=i){ //交換R[i]和R[k]  
        R[0]=R[i]；R[i]=R[k]；R[k]=R[0]； //R[0]作暫存單元  
       } //endif  
    } //endfor  
 } //SeleetSort  

算法分析

（1）關(guān)鍵字比較次數(shù)

無(wú)論文件初始狀態(tài)如何，在第 i 趟排序中選出最小關(guān)鍵字的記錄，需做 n-i 次比較，因此，總的比較次數(shù)為： n(n-1)/2=O(n2)

（2）記錄的移動(dòng)次數(shù)

當(dāng)初始文件為正序時(shí)，移動(dòng)次數(shù)為 0

文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，總的移動(dòng)次數(shù)取最大值 3(n-1)。

直接選擇排序的平均時(shí)間復(fù)雜度為 O(n2)。

（3）直接選擇排序是一個(gè)就地排序

（4）穩(wěn)定性分析

直接選擇排序是不穩(wěn)定的

【例】反例[2，2，1]