選擇排序分析

一.選擇排序原理

　　1.每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置

　　2.再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到剛才已排序序列的後面。

　　3.以此類推，直到全部待排序的資料元素排完。 

　　選擇排序是不穩定的排序方法。例如：序列3，3，2，1， 我們知道第一次周遊的時候，選擇最後一個元素1和第一個元素3交換，那麼原序列中2個3的相對前後順序就和之前不一樣了，是以選擇排序不是一個穩定的排序算法。

二.選擇排序時間複雜度

　　第一次循環比較 n - 1次，第二次循環比較 n - 2次，依次類推，最後一個元素不需要比較，是以共進行 n - 1次循環，最後一次循環比較1次。

　　是以一共比較1 + 2 + 3 + ... +（n - 2）+（n - 1）次，求和得n2/2 - n / 2 ，忽略系數，取最高指數項，該排序的時間複雜度為O(n2)

三.代碼實作(Java)

//實作選擇排序
public class Test02 {
  public static void main(String[] args) {
      int[] arr = {1,3,2,5,4,9,6};
      selectSort(arr);
      System.out.println(Arrays.toString(arr));
  }
  public static void selectSort(int[] arr){
      if((arr==null)||(arr.length==0)){
          try{
            throw new MyException("出現了數組為空的異常");
        } catch (MyException e) {
            e.printStackTrace();
        }
          return;
      }
      int minIndex = 0;//暫未排序的最小資料的下标
      int temp = 0;//将被交換位置的那個元素
      for(int i = 0 ; i < arr.length ; i++){
          minIndex=i;
          for(int j = i + 1 ; j < arr.length ; j++){//在暫未排序的區域中找到最小資料并儲存其下标
              if(arr[j]<arr[minIndex]){//兩者中較小的元素的下标賦給minIndex
                  minIndex=j;
              }
          }
          //将最小元素放到本次循環的前端
          temp=arr[i];
          arr[i]=arr[minIndex];
          arr[minIndex]=temp;
      }
  }
}
class MyException extends Exception{
    
    public MyException() {
    }
    public MyException(String msg) {
        super(msg);
    }
}      

 測試結果如下