[演算法] 選擇排序法 Selection Sort

　　選擇排序法是經典的三大 O(n^2) 排序演算法之一。所謂的「選擇」是要在未排列序列中最小(大)的物件，將其放置到已排列序列的末端。(一個序列可分為兩段，已排序和未排序)，重複此動作最後就能完成排序。

　　雖然會說選擇排序法有一個優點是最壞狀況的「交換」次數是 n - 1 次，在交換位置的時間比比較大得多的情況下，故若數列接近反序，選擇排序法會比冒泡排序法跟選擇排序法來得有效率，但實際上在實作時是錯的。由於尋找最小值時就會不斷需要記住最小值的索引，會一直進行賦值操作，故在實際使用上(測試過整數完全反序數列排序)，插入排序法效率遠比選擇排序法來得高。

複雜度：

• 時間：最佳 O(n^2) 最差 O(n^2)
• 空間：O(n), O(1) 輔助

步驟：

1. 將序列視為兩段，已排序和未排序，一開始整個數列都算未排序。
2. 從未排序序列的頭開始向後尋找最大(小)的物件。
3. 將其與未排序數列的頭交換 (也就是將這個物件放到已排序數列的尾端)。
4. 重複此步驟2~3，直到整個數列都變成已排序數列。

Java 簡單實現：

public class SelectionSort {
     public void sort(int[] array) {
          // 未排序數列的頭
          for(int i = 0; i < array.length; ++i) { 
               int min = i;
               // 向後找最大(小)
               for(int j = i + 1; j < array.length; ++j) {  
                    if(array[j] < array[min]) {
                         min = j;
                    }
               }
               // 和頭交換
               int tmp = array[i];
               array[i] = array[min];
               array[min] = tmp;
          }
     }
}

範例影片：

參考資料：

1. Wiki 選擇排序法