1. 選擇排序思想
（1.1）選擇排序的基本思想是：每一趟（例如第i趟）在后面n-i+1(i=1,2, ... , n)個待排序元素中選取關鍵字最小的元素，作為有序子序列的第i個元素，直到第n-1趟做完，待排序元素只剩下1個，就不用再選了，選擇排序中的堆排序演算法是重點內容，
2. 簡單選擇排序的思想
（2.1）從上面選擇排序的思想中可以很直觀第得出簡單選擇排序演算法的思想：假設排序表為L[1 ... n], 第i趟排序即從L[i ... n]中選擇關鍵字最小的元素與L[i] 交換，每一趟排序可以確定一個元素的最終位置，這樣經過n-1趟排序就可以使得整個待排序表有序，
3. 簡單選擇排序代碼實作
1 package cn.sun.it.review; 2 3 import java.util.Arrays; 4 import java.util.Scanner; 5 6 public class SelectSort { 7 8 public static void main(String[] args) { 9 System.out.println("請輸入若干個整數，以逗號分隔："); 10 Scanner sc = new Scanner(System.in); 11 String strNums = sc.nextLine(); 12 String[] tempArrNums = strNums.split(","); 13 int[] arr = new int[tempArrNums.length]; 14 for (int i = 0; i < arr.length; i++) { 15 arr[i] = Integer.valueOf(tempArrNums[i]); 16 } 17 System.out.println("排序前：" + Arrays.toString(arr)); 18 selectSort_v1(arr); 19 System.out.println("排序后：" + Arrays.toString(arr)); 20 } 21 22 private static void selectSort_v1(int[] arr) { 23 int min; 24 int temp; 25 for(int i=0;i<arr.length-1;i++){ // 一共進行n-1趟排序 26 min = i; // 記錄最小元素的位置 27 for(int j=i+1;j<arr.length;j++){ // 在arr[i...n-1]中選擇最小的元素 28 if(arr[j]<arr[min]){ 29 min = j; // 更新最小元素的位置 30 } 31 } 32 if(min != i){ // 與第i個位置進行交換 33 temp = arr[i]; 34 arr[i] = arr[min]; 35 arr[min] = temp; 36 } 37 } 38 } 39 40 }
4. 測驗結果
5. 性能分析
（5.1）空間效率：僅使用常數個輔助單元，故而空間效率為O(1);
（5.2）時間效率：從上述代碼中可以看出，在簡單選擇排序程序中，元素移動的操作次數很少，不會超過3(n-1)次，最好的情況是移動0次，此時對應的表已經有序；但元素間比較的次數與序列的初始狀態無關，始終是n(n-1)/2次，所以時間復雜度始終是O(n2)
（5.3）穩定性：在第i趟找到最小的元素后，和第i個元素交換，可能會導致第i個元素與其含有相同關鍵字元素的相對位置發生改變，例如，表L={2,2,1}，經過一趟排序后，
L={1,2,2}，最終排序序列也是L={1,2,2}，顯然，2與2 的相對次序已經發生了變化，因此，簡單選擇排序是一個不穩定第排序方法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270604.html
標籤：Java
上一篇：Spring 事務介紹
下一篇：Java 執行緒池詳解