Day18:[排序演算法]Selection Sort - 选择排序法

其实插入排序法就很像平时我们在玩扑克牌时整理牌组的行为，将扑克牌依照大小插入对应的位置，插入排序法的流程是从第2个位置开始与左边的数字(位置1)比较，然後就依循着以下的规则，与左边的元素比大小，并且插入到正确的位置，直到全部的元素的由小排到大。

假设有个阵列为 [40 , 13 , 20 , 8]

从第二个位置开始，13与40相比13比较小，因此把13插入到40之前

此时阵列为[13 , 40, 20 , 8]
再来轮到20，20大於13且小於40 ，所以就将20插入到13和40之间

此时阵列为[13 , 20, 40 , 8]
最後轮到8 ，与前面三个元素相比为最小值，所以就插入到最前面

此时阵列为[8, 13 , 20, 40]

连续的步骤会如下图所示

图档来源:https://visualgo.net/zh/

用js实作插入排序法:

const insertionSort = (arr) => {
    //因为要跟左边数字比大小所以回圈的从1开始 (i=0的话没有左边的数字)
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        //左边的数字index - 1
        let point = i - 1;
        //检查左边数字是否大於现在的数字
        while (point >= 0 && arr[point] > current) {
            arr[point + 1] = arr[point];
            point--;
        }
        arr[point + 1] = current;
    }
    return arr;
};

insertionSort([40, 13, 20, 8]);