Day 26： Insertion sort & Selection sort

我们先来用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