排序 - 選擇排序 - 直接選擇排序

　　選擇排序(Selection Sort)的基本思想是每一趟從待排序的記錄中選出關鍵字最小的記錄順序放在已排好序的子文件的最後

　　直到全部記錄排序完畢

　　常用的選擇排序方法有直接選擇排序和堆排序

　　直接選擇排序(Straight Selection Sort)

　　直接選擇排序的基本思想

　　n個記錄的文件的直接選擇排序可經過n趟直接選擇排序得到有序結果

　　①初始狀態無序區為R[n]有序區為空

　　②第趟排序

　　在無序區R[n]中選出關鍵字最小的記錄R[k]將它與無序區的第個記錄R[]交換使R[]和R[n]分別變為記錄個數

　　增加個的新有序區和記錄個數減少個的新無序區

　　……

　　③第i趟排序

　　第i趟排序開始時當前有序區和無序區分別為R[i]和R[in](≤i≤n)該趟排序從當前無序區中選出關鍵字最小

　　的記錄R[k]將它與無序區的第個記錄R[i]交換使R[i]和R[i+n]分別變為記錄個數增加個的新有序區和記錄個數減少

　　個的新無序區

　　這樣n個記錄的文件的直接選擇排序可經過n趟直接選擇排序得到有序結果

　　直接選擇排序的過程

　　對初始關鍵字為和 的文件進行直接選擇排序的過程【 參見動畫演示 】

　　算法描述

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

　　void SelectSort(SeqList R)

　　{

　　int ijk;

　　for(i=;i

　　k=i;

　　for(j=i+1;j<=n;j++) //在當前無序區R[i..n]中選key最小的記錄R[k]

　　if(R[j].key

　　k=j; //k記下目前找到的最小關鍵字所在的位置

　　if(k!=i){ //交換R[i]和R[k]

　　R[0]=R[i];R[i]=R[k];R[k]=R[0]; //R[0]作暫存單元

　　} //endif

　　} //endfor

　　} //SeleetSort

　　4、算法分析

　　(1)關鍵字比較次數

　　無論文件初始狀態如何，在第i趟排序中選出最小關鍵字的記錄，需做n-i次比較，因此，總的比較次數為：

　　n(n-1)/2=0(n 2 )

　　(2)記錄的移動次數

　　當初始文件為正序時，移動次數為0

　　文件初態為反序時，每趟排序均要執行交換操作，總的移動次數取最大值3(n-1)。tw.WiNgWIt.Com

　　直接選擇排序的平均時間復雜度為O(n 2 )。

　　(3)直接選擇排序是一個就地排序

　　(4)穩定性分析

　　直接選擇排序是不穩定的

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23782.html