数组和算法-数组排序-插入排序

插入排序

今天来聊聊插入排序，我们还是先说它的思想

基本思想：我们可以把数组的每一个值，想象成扑克牌，这样更实物化，更形象化一点。我们从数组中拿出第一张牌，放在左手，以后拿到每一张牌的时候和左手中的牌进行比较(一般来说，我们是从后往前比)，如果你拿到的当前的牌比倒数第一张小，再继续往左比。。。，一直到遇到当前的牌比某张牌打了，则把这张牌插入到某张牌的后边(也就是说某张牌下一张牌的前面)

说完思想直接上程序吧，因为前面说了两个排序方法，第三个大家应该能看懂

var ary = [6,3,5,7,2,4];
    function insertSort(ary) {
        var newAry = [];//存储的是左手中的牌
        newAry.push(ary[0]);//先抓第一张牌
        // 依次把桌面的牌抓到按照基本思想进行比较
        for(var i=1;i<ary.length;i++){
            var cur = ary[i];//抓到的当前的牌，然后从后往前和左手中的牌进行比较
            for(var j=newAry.length-1;j>=0;){//要和左手的牌，进行一个一个比较，因此要循环左手的牌(从后往前循环)
                if(cur<newAry[j]){ //当前新牌比左手中的这张牌小，继续和newAry[j]前面的一张牌进行比较
                    j--;
                    if(j==-1){// 说明当前的牌比左手中的牌都小，我们就把这张牌放在左手的开头位置即可
                        newAry.unshift(cur);
                    }
                }else {//当前新牌比左手中的这张牌大，则放在这张牌的后面,也相当于newAry[j+1]的前面
                    newAry.splice(j+1,0,cur);
                    break;// 跳出此for循环的程序段;不影响上一个for程序段
                }
            }
        }
        return newAry;
    }
    var res = insertSort(ary);
    console.log(res);

结果为 [2, 3, 4, 5, 6, 7]