Java經典算法匯總之選擇排序（SelectionSort）。本站提示廣大學習愛好者：（Java經典算法匯總之選擇排序（SelectionSort））文章只能為提供參考，不一定能成為您想要的結果。以下是Java經典算法匯總之選擇排序（SelectionSort）正文
a)道理：每趟從待排序的記載當選出最小的元素，次序放在已排好序的序列最初，直到全體記載排序終了。也就是：每趟在n-i+1(i=1，2，…n-1)個記載當選取症結字最小的記載作為有序序列中第i個記載。基於此思惟的算法重要有簡略選擇排序、樹型選擇排序和堆排序。（這裡只引見經常使用的簡略選擇排序）
b)簡略選擇排序的根本思惟：給定命組：int[]arr={外面n個數據}；第1趟排序，在待排序數據arr[1]~arr[n]當選出最小的數據，將它與arrr[1]交流；第2趟，在待排序數據arr[2]~arr[n]當選出最小的數據，將它與r[2]交流；以此類推，第i趟在待排序數據arr[i]~arr[n]當選出最小的數據，將它與r[i]交流，直到全體排序完成。
c)舉例：數組int[]arr={5,2,8,4,9,1};
-------------------------------------------------------
第一趟排序： 原始數據：528491
最小數據1，把1放在首位，也就是1和5交換地位，
排序成果：128495
-------------------------------------------------------
第二趟排序：
第1之外的數據{28495}停止比擬，2最小，
排序成果：128495
-------------------------------------------------------
第三趟排序：
除1、2之外的數據{8495}停止比擬，4最小，8和4交流
排序成果：124895
-------------------------------------------------------
第四趟排序：
除第1、2、4之外的其他數據{895}停止比擬，5最小，8和5交流
排序成果：124598
-------------------------------------------------------
第五趟排序：
除第1、2、4、5之外的其他數據{98}停止比擬，8最小，8和9交流
排序成果：124589
-------------------------------------------------------
注：每趟排序取得最小數的辦法：for輪回停止比擬，界說一個第三個變量temp，起首前兩個數比擬，把較小的數放在temp中，然後用temp再去跟剩下的數據比擬，假如湧現比temp小的數據，就用它取代temp華夏有的數據。詳細參照前面的代碼示例，信任你在學排序之前曾經學過for輪回語句了，如許的話，這裡懂得起來就特殊輕易了。
代碼示例：
//選擇排序
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+" ");
}
//選擇排序的優化
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; //記下今朝找到的最小值地點的地位
}
}
//在內層輪回停止，也就是找到本輪輪回的最小的數今後，再停止交流
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+" ");
}
}
}
運轉成果截圖：
選擇排序的時光龐雜度：簡略選擇排序的比擬次數與序列的初始排序有關。假定待排序的序列有N個元素，則比擬次數永久都是N(N-1)/2。而挪動次數與序列的初始排序有關。當序列正序時，挪動次數起碼，為0。當序列反序時，挪動次數最多，為3N(N-1)/2。
所以，綜上，簡略排序的時光龐雜度為O(N2)。
