原理：每一趟從待排序的記錄中選出最小的元素界阁，順序放在已排好序的序列最后，直到全部記錄排序完畢挂据。也就是：每一趟在n-i+1(i=1以清，2，…n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄棱貌【撩模基于此思想的算法主要有[簡(jiǎn)單選擇排序]箕肃、樹型選擇排序和[堆排序]
簡(jiǎn)單選擇排序的基本思想：給定數(shù)組：int[] arr={里面n個(gè)數(shù)據(jù)}婚脱；第1趟排序，在待排序數(shù)據(jù)arr[1]arr[n]中選出最小的數(shù)據(jù)勺像，將它與arrr[1]交換障贸；第2趟，在待排序數(shù)據(jù)arr[2]arr[n]中選出最小的數(shù)據(jù)吟宦，將它與r[2]交換篮洁；以此類推，第i趟在待排序數(shù)據(jù)arr[i]~arr[n]中選出最小的數(shù)據(jù)殃姓，將它與r[i]交換袁波，直到全部排序完成。
舉例：數(shù)組 int[] arr={5,2,8,4,9,1};
第一趟排序： 原始數(shù)據(jù)：5 2 8 4 9 1
最小數(shù)據(jù)1蜗侈，把1放在首位篷牌，也就是1和5互換位置，
排序結(jié)果：1 2 8 4 9 5
第二趟排序：
第1以外的數(shù)據(jù){2 8 4 9 5}進(jìn)行比較踏幻，2最小枷颊，
排序結(jié)果：1 2 8 4 9 5
第三趟排序：
除1、2以外的數(shù)據(jù){8 4 9 5}進(jìn)行比較该面，4最小夭苗，8和4交換
排序結(jié)果：1 2 4 8 9 5
第四趟排序：
除第1、2隔缀、4以外的其他數(shù)據(jù){8 9 5}進(jìn)行比較题造，5最小，8和5交換
排序結(jié)果：1 2 4 5 9 8
第五趟排序：
除第1猾瘸、2界赔、4桥嗤、5以外的其他數(shù)據(jù){9 8}進(jìn)行比較，8最小仔蝌，8和9交換
排序結(jié)果：1 2 4 5 8 9
注：每一趟排序獲得最小數(shù)的方法：for循環(huán)進(jìn)行比較泛领，定義一個(gè)第三個(gè)變量temp，首先前兩個(gè)數(shù)比較敛惊，把較小的數(shù)放在temp中渊鞋，然后用temp再去跟剩下的數(shù)據(jù)比較，如果出現(xiàn)比temp小的數(shù)據(jù)瞧挤，就用它代替temp中原有的數(shù)據(jù)锡宋。具體參照后面的代碼示例，相信你在學(xué)排序之前已經(jīng)學(xué)過for循環(huán)語句了特恬，這樣的話执俩，這里理解起來就特別容易了。
代碼示例：
public class SelectionSort {
public static void main(String[] args) {
int[] arr={1,3,2,45,65,33,12};
System.out.println("交換之前：");
for(int num:arr){
System.out.print(num+" ");
} //選擇排序的優(yōu)化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 選最小的記錄
if(arr[j] < arr[k]){
k = j; //記下目前找到的最小值所在的位置
}
} //在內(nèi)層循環(huán)結(jié)束癌刽，也就是找到本輪循環(huán)的最小的數(shù)以后役首，再進(jìn)行交換
if(i != k){ //交換a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交換后：");
for(int num:arr){
System.out.print(num+" ");
}
}
}
運(yùn)行結(jié)果：
交換之前：1,3,2,45,65,33,12
交換后：1,2,3,12,33,45,65
選擇排序的時(shí)間復(fù)雜度：簡(jiǎn)單選擇排序的比較次數(shù)與序列的初始排序無關(guān)。 假設(shè)待排序的序列有 N 個(gè)元素显拜，則比較次數(shù)永遠(yuǎn)都是N (N - 1) / 2衡奥。而移動(dòng)次數(shù)與序列的初始排序有關(guān)。當(dāng)序列正序時(shí)远荠，移動(dòng)次數(shù)最少，為 0档址。當(dāng)序列反序時(shí)邻梆，移動(dòng)次數(shù)最多，為3N (N - 1) / 2确虱。
所以，綜上窘问，簡(jiǎn)單排序的時(shí)間復(fù)雜度為 O(N2)。
