插入排序算法

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。
举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的。然后3要插到5前面，把5后移一位，变成3,5,8,6,4。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。
注意在插入一个数的时候要保证这个数前面的数已经有序。
简单插入排序的时间复杂度也是O(n^2)。

/**
 * 插入排序，默认第一个最小
 * @param {Array<Number>} arry 要排序的数组
 */
function insertSort(arry: Array<Number>): Array<Number> {
    if (arry.length == 0) {//判断数组不为空
        return [];
    }

    for (let i = 1; i < arry.length; i++) {//从1开始，默认第一个最小
        for (let j = i; j < arry.length; j++) {
            let temp = arry[i - 1];//要比较插入的对象
            if (temp > arry[j]) {//交换
                arry[i - 1] = arry[j];
                arry[j] = temp;
            }
            console.log(JSON.stringify(arry))
        }
    }
    return arry;
}

结果：