3.插入排序（insertSort）

描述

数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1; 数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3;

如果数据序列基本有序，使用插入排序会更加高效。

• 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

实现

var insetSort = function(nums) {
    var temp = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        // 只排序当下这个分区
        for (let j = i + 1; j >= 0; j--) {
            if (nums[j] < nums[j - 1]) {
                temp = nums[j - 1];
                nums[j - 1] = nums[j];
                nums[j] = temp;
            }
        }
    }
    return nums;
};