選擇類排序法

1435 1435 i

選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。我們主要介紹簡單選擇排序、樹型選擇排序和堆排序。
簡單選擇排序的基本思想：第i趟簡單選擇排序是指通過n-i次關鍵字的比較，從n-i+1個記錄中選出關鍵字最小的記錄，並和第i個記錄進行交換。共需進行i-1趟比較，直到所有記錄排序完成為止。例如：進行第i趟選擇時，從當前候選記錄中選出關鍵字最小的k號記錄，並和第i個記錄進行交換。圖9.5給出了一個簡單選擇排序示例，說明了前三趟選擇後的結果。圖中大括弧內為當前候選記錄，大括弧外為當前已經排好序的記錄。
｛ 48　62 35 77 55 14 35 98　｝
↑　↑
i k
14　｛ 62 35 77 55 48 35 98　｝
↑　↑
i k
14　35 ｛ 62 77 55 48 35 98　｝
↑　↑
i k
14　35 35 ｛ 77 55 48 62 98　｝
↑　↑
i k
選擇排序示例
簡單選擇排序的算法具體描述如下：
void SelectSort(RecordType r[], int length)
/*對記錄數組r做簡單選擇排序，length為數組的長度*/
{
n=length;
for ( i=1 ; i<= n－１; i++)
{
k=i；
for ( j=i+1 ; j<= n ; j++)
if (r&#91;j&#93;.key < r&#91;k&#93;.key ) k=j；
if ( k!=i)
{ x= r&#91;i&#93;； r&#91;i&#93;= r&#91;k&#93;； r&#91;k&#93;=x; }
}
} /* SelectSort */

算法

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