選擇排序原理 每一趟從待排序的記錄中選出最小的元素汉买，順序放在已排好序的序列最后，直到全部記錄排序完畢伟件。也就是：每一趟在n-i+1(i=1戈毒，2艰猬，…n-1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄÷袷校基于此思想的算法主要有簡單選擇排序冠桃、樹型選擇排序和堆排序。（這里只介紹常用的簡單選擇排序）
簡單選擇排序的基本思想：給定數(shù)組：int[] arr={里面n個數(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}進行比較，2最小章喉，
排序結(jié)果：1 2 8 4 9 5
第三趟排序：
除1汗贫、2以外的數(shù)據(jù){8 4 9 5}進行比較，4最小秸脱，8和4交換
排序結(jié)果：1 2 4 8 9 5
第四趟排序：
除第1落包、2、4以外的其他數(shù)據(jù){8 9 5}進行比較摊唇，5最小咐蝇，8和5交換
排序結(jié)果：1 2 4 5 9 8
第五趟排序：
除第1、2巷查、4有序、5以外的其他數(shù)據(jù){9 8}進行比較，8最小岛请，8和9交換
排序結(jié)果：1 2 4 5 8 9
注：每一趟排序獲得最小數(shù)的方法：for循環(huán)進行比較旭寿，定義一個第三個變量temp，首先前兩個數(shù)比較崇败，把較小的數(shù)放在temp中盅称，然后用temp再去跟剩下的數(shù)據(jù)比較，如果出現(xiàn)比temp小的數(shù)據(jù)后室，就用它代替temp中原有的數(shù)據(jù)缩膝。具體參照后面的代碼示例，相信你在學排序之前已經(jīng)學過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ù)以后云芦，再進行交換
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+" ");
}
}
運行結(jié)果
選擇排序的時間復雜度：簡單選擇排序的比較次數(shù)與序列的初始排序無關(guān)俯逾。 假設(shè)待排序的序列有 N 個元素，則比較次數(shù)永遠都是N (N - 1) / 2舅逸。而移動次數(shù)與序列的初始排序有關(guān)桌肴。當序列正序時，移動次數(shù)最少琉历，為 0坠七。當序列反序時，移動次數(shù)最多旗笔，為3N (N - 1) / 2彪置。所以，綜上蝇恶，簡單排序的時間復雜度為 O(N2)拳魁。
