我們先來用insertion sort algorithm來解題。
雖然他的效率也不高，但這是很好理解且實作的演算法。
偷渡一下隊友的一篇好文 演算法入門理解
下面我就直接敘述insertion sort實作的流程！

先隨便給一個陣列 Array = [5, 2, 3, 9, 3]
我們從陣列中第一個元素開始拜訪，

1. [ 5 ]

   先把5暫定在第一個位置，接著往第２個數拜訪
   可以想像我們用一個sublist來當作已經排序好的數列

2. [ 5, 2]
   因為 5 > 2，所以兩個交換(swap)

3. [ 2, 5] 接著繼續到第3個數

4. [ 2, 5, 3] 因為 5 > 3，所以 swap
   [ 2, 3 ,5] 然後2!>3，所以不動

5. [ 2, 3, 5, 9] 因為5 !> 9，不用動
   且前面3個數都已經是排序過的，就不用再做檢查

6. 自己試試看最後一步應該會是怎麼樣swap吧！

應該是 [ 2, 3, 5, 9, 3] → [ 2, 3, 5, 3, 9] → [ 2, 3, 3, 5, 9] 對吧？

很明顯我們上面的操作都是in place ,所以 空間複雜度O(1)
而平均時間複雜度會是 O(n^2)， n是我們array的長度

最後來看程式碼的實作

function insertionSort(array) {
  for( let i = 1; i < array.length; i++){
//一開始 tmp = 1 取 array[1] 和 array[0]比較
		let tmp = i;
		while(tmp > 0 && array[tmp] < array[tmp - 1]){
			swap(tmp, tmp-1, array);
			tmp -= 1;
		}
	}
	return array;
}

const swap = (i, j, array) =>{
	const tmp = array[j];
	array[j] = array[i];
	array[i] = tmp;
}

看完Insertion sort，直接來看Selection sort的執行步驟。

我們一開始就看整個陣列，代表著完全尚未被排序的陣列[5, 2, 3, 9, 3] (目前是整個陣列都是unsorted subarray)
我們把整個array非排序過的數上個色
[ 5, 2, 3, 9, 3 ]

接著我們掃過整個array，取出最小的數，把他和array中還沒被排序的sublist第一個數交換(swap)。

第一回合中，我們找到2。於是我們就把 2 和 5 swap

[2 , 5, 3, 9, 3 ] 現在２就是我們已經排序過的sublist，
而剩下的就是我們尚未排序的sublist。

第二回合，我們找到 3，所以再把 3,5 swap 得到 [2 , 3, 5, 9, 3 ]

接著同理操作 [2 , 3, 3, 9, 5 ] → [2 , 3, 3, 5, 9 ] → [2 , 3, 3, 5, 9 ]
很明顯我們上面的操作都是in place ，所以 空間複雜度O(1)
而平均時間複雜度會是 O(n^2)， n是我們array的長度

最後來看程式碼的實作

function selectionSort(array) {
  let startIndex = 0;
  while (startIndex < array.length - 1) {
    //紀錄最小數字的index
    let smallestNumIndex = startIndex;
    for (let i = startIndex + 1; i < array.length; i++) {
      if (array[smallestNumIndex] > array[i]) smallestNumIndex = i;
    }
    swap(startIndex, smallestNumIndex, array);
    startIndex++;
  }
  return array;
}

const swap = (i, j, array) => {
  const tmp = array[j];
  array[j] = array[i];
  array[i] = tmp;
};

不知道有沒有人跟我一樣一開始學這兩個算法時，超常把他們搞相反！
建議大家也多coding幾次，雖然每次都是選最小的數來交換位置，但最大的差異是一開始在挑選比較的樣本基準上不一樣喔。

明日預告：Quick Sort