選擇排序的基本操作就是每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。算法不穩(wěn)定，O(1)的額外的空間，比較的時(shí)間復(fù)雜度為O(n^2)，交換的時(shí)間復(fù)雜度為O(n)，并不是自適應(yīng)的。在大多數(shù)情況下都不推薦使用。只有在希望減少交換次數(shù)的情況下可以用。

基本思想

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

①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。 　　

②第1趟排序 　　

在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。 　　

……

 ③第i趟排序 　　

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

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

代碼實(shí)現(xiàn)

public class Test {   
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 預(yù)設(shè)數(shù)據(jù)數(shù)組   
public static void main(String args[]) {   
int i; // 循環(huán)計(jì)數(shù)變量   
int Index = a.length;// 數(shù)據(jù)索引變量   
System.out.print("排序前: ");   
for (i = 0; i < Index - 1; i++)   
System.out.printf("%3s", a);   
System.out.println("");   
SelectSort(Index - 1); // 選擇排序   
// 排序后結(jié)果   
System.out.print("排序后: ");   
for (i = 0; i < Index - 1; i++)   
System.out.printf("%3s", a);   
System.out.println("");   
}   
public static void SelectSort(int Index) {   
int i, j, k; // 循環(huán)計(jì)數(shù)變量   
int MinValue; // 最小值變量   
int IndexMin; // 最小值索引變量   
int Temp; // 暫存變量   
for (i = 0; i < Index - 1; i++) {   
MinValue = 32767; // 目前最小數(shù)值   
IndexMin = 0; // 儲存最小數(shù)值的索引值   
for (j = i; j < Index; j++) {   
if (a[j] < MinValue) // 找到最小值   
{   
MinValue = a[j]; // 儲存最小值   
IndexMin = j;   
}   
Temp = a; // 交換兩數(shù)值   
a = a;   
a = Temp;   
}   
System.out.print("排序中: ");   
for (k = 0; k < Index; k++)   
System.out.printf("%3s", a[k]);   
System.out.println("");   
}   
}   
} 

選擇排序法與冒泡排序法一樣，最外層循環(huán)仍然要執(zhí)行n-1次，其效率仍然較差。

【編輯推薦】

1. 5.5.5 使用直接選擇排序法
2. C#算法之選擇排序淺析
3. 經(jīng)典四講貫通C++排序之四 選擇排序