什么是插入排序

先看一下百度百科的定义：
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序的基本思路是，除数组的第一个元素外，对数组中每个元素进行遍历，比较前面元素与当前元素的大小关系，然后将当前元素插入到前面小于（或大于）当前元素的位置，插入排序出如下。

arr = [6,3,2,5,4,1] 数组arr是待排序的数组，首先取出数组中第二个元素 3 ，去比较前一个元素 6 ，3 比 6 小所有把 3 插入到 6 前面，然后取出数组的第三个元素 2 ，去比较前一个元素 6 ，2 比 6 小再比较 6 前面元素 3 ，2 比 3 小所有 2 插入到 3 前面。依次类推，完成整个数组的排序。

插入排序的代码实现

为了方便理解这里先不用两层循环的代码：

        Array.prototype.insertionSort = function() {  //挂载到原型链上
            for (var i = 1; i < arr.length; i++) {    //i 表示要插入的元素索引
                for(var j = i - 1; j >= 0; j--){      //j 表示要插入元素前一项的索引
                    if(arr[j] < arr[i]){             //比较当前元素，与前面所以元素  
                       break        //前一个元素小于当前元素，找到插入位置，终止本次遍历 
                    }
                }
                var temp = arr[i]  //存入arr[i]的值
                for ( var k = i - 1; k > j; k--){ 
                    arr[k + 1] = arr[k]  //将所以比arr[i]大的数据向后移
                }
                arr[k + 1] = temp //将arr[i]放到正确位置上
            }
        }
        var arr = [6,3,2,5,4,1]
        arr.insertionSort()
        console.log(arr)

控制台正常输出：

控制台输出的执行过程，以及结果符合预期，说明上面代码没有错误。但上面的代码有三层循环，所有我们再来给它优化一下。

插入排序优化

我们将内层的两个循环优化一下。

   Array.prototype.insertionSort = function() {  //挂载到原型链上
            for (var i = 1; i < arr.length; i++) {
                var j = i - 1       //j 表示要插入元素前一项的索引
                var temp = arr[i]   //存入arr[i]的值
                while(j >= 0 && arr[j] > temp) {   //比较当前元素，与前面所以元素
                    arr[j+1] = arr[j]  //将所以比arr[i]大的数据向后移
                    j--
                }
                arr[j+1] = temp
                console.log(arr)
            }
        }
        var arr = [6,3,2,5,4,1]
        arr.insertionSort()
        console.log(arr)

控制台输出成功：

插入排序的时间复杂度和稳定性

• 插入排序的时间复杂度是O(n^2)；
• 插入排序是稳定的排序算法；

结语

本小节到此结束，谢谢大家的观看！

如有问题欢迎各位指正

记得点赞 + 收藏。