前言

前一章節講了初等排序的 Insertion sort，接下來要介紹的也是同為初等排序的 Selection Sort。剛開始，我們也是要先從觀念開始講起，才會帶到演算法和時間複雜度～

觀念

我們從最一開始的 index 開始，讓他往後找到擁有最小值的 index，便與他交換，我們看到下圖，每一回合會與後面 index 之最小值點作交換

演算法

我們看完觀念之後，我們可以開始思考要怎麼進行，只要用第一個迴圈去選擇目前想比較的 index 為何(n-1回合)，接下來再從他後面的 index 找出最小點即可

selectionSort(int[] a){
    int n = a.length;
    for(int i=0;i<=n-1;i++){
        int min = i;
        for(int j=i+1;j<=n;j++){
            if(a[min] > a[j]) 
                min = j;
        }
    }
    if (i!=min) swap(a[i],a[min]);
}

時間複雜度

O(n^2)

Stable or Unstable

我們來看下圖的狀況

由 if (a[min] > a[j])來看，會造成上圖此狀況，我們只要找到一個反例，就可以證明其為 unstable