算法（二）--插入排序

在说插入排序之前我想和大家说一下，算法的一些基本概念，
如下：

• 时间复杂度指的是一个算法执行所耗费的时间
• 空间复杂度指运行完一个程序所需内存的大小
• 稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
• 不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

插入排序基本思想

从数组的第二项开始考察，把数组的第二项和第一项做比较如果第二项比第一项大就不管，如果比第一项小就交换位置，接着考察第三项，先将第三和第二比较，如果第三比第二大退出循环，如果第三比第二小交换位置继续和第一项比较，大则退出当前循环，小则交换位置。依次类推。。
可以将其想象为打扑克时的理牌方式。
代码如下：

/**
 * 插入排序方法
 * @param {* 需要排序的数组} arr 
 * @param {* 数组的长度} n 
 */
insertionSort = (arr, n) => {
    for (let i = 1; i < n; i++) {
        //寻找arr[i]合适的插入位置,所以需要遍历之前比较过的数据
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                //变量结构赋值 测试10000数据的时候预计多消耗.3s的性能
                // [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]

                var temp = arr[j - 1]
                arr[j - 1] = arr[j]
                arr[j] = temp
            } else {
                break
            }
        }
    }
}

代码上没有什么难点，就是给考察对象选择合适的位置，一遍一遍去交换位置，找到合适的位置以后退出当前循环，按照我们的想法能退出循环应该比选择排序要快吧，根据实际测试，比选择排序要慢一点，应该是交换操作过多造成的。
根据想法优化，代码如下：

 //插入排序优化写法,将比较后互换位置 变成寻找位置并赋值
//对于插入排序在排序一个近乎有序的数组时效率可以达到O(n)级
this.insertionSort1 = (arr, n) => {
    for (let i = 1; i < n; i++) {
        //寻找arr[i]合适的插入位置,所以需要遍历之前比较过的数据
        let e = arr[i];
        let j
        for (j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1]
        }
        arr[j] = e
    }
}

以上代码实际测试比选择排序要稍微快一点，插入排序是一个可以达到O(n)级别的算法，应用比较广泛。基本大多数的高级算法，底层优化都可以用插入排序。

以上都是个人理解如有不对之处还望指正交流！