分解javascript 插入排序算法

掌握算法，先理解原理

插入排序.gif

理解：
我们可以抽象成玩牌，我们把牌分成两组、每抽一张牌的时候，总会给牌排序
上图中橘色的是手里排好序的牌，蓝色的是准备拿到手里排序的牌，
每拿起一张蓝牌 然后 从大到小扫描橘牌，逐级将大的往后挪，之后将蓝牌插入到合适的位
置

原理图

代码实现

外部循环：未排好序的部分
内部循环：每要给一张牌排序的操作，从大到小循环排好序的牌，如果准备插入的值小于最后一张，则将该元素往后移，依次查找，否则直接插入

var array = [1,2,3]
function insertionSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        //i : 未排序部分的当前位置
        value = arr[i]   // 准备插入的值（新牌）
        // j: 已排序部分的当前位置
        //  var j = i - 1 , 已经排好序最后一个元素位置
        //如果当已排序部分的当前元素大于value
        for (var j = i - 1; j > -1 && arr[j] > value; j--) {
            arr[j + 1] = arr[j]    //将当前元素向后移一位，再将前一位与value比较
        }
        //否则直接插入，新牌落位
        arr[j + 1] = value
    }
    return arr
}

insertionSort(array)
console.log(array)

逆序对

对于下标i<j,如果 A[i] > A[j],则称（i，j） 是一对逆序对
例如：{34,8,64,51}中的逆序对有
（34，8）(64 , 51)

时间复杂度

（冒泡和插入）交换2个相邻元素正好消去1个逆序对！
T(N,I) =O(N+I) N是数组个数，I 是逆序对个数
如果序列基本有序，那么插入排序简单高效

 定理：任意N个不同元素组成的序列平均具有N ( N - 1 ) / 4 个逆序对。
 定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为 O( N^ 2) 。
 这意味着：要提高算法效率，我们必须

每次消去不止1个逆序对！ 并且 每次交换相隔较远的2个元素

这样就有了 ----- 希尔排序