【前端面试】（十二）JavaScript插入排序

就是在把关键字temp通过比较大小，插入到前面已经排好序的序列中，直到全部元素插入完成。

1. 是否为数组->数组是否为空
2. 默认序列下标0的数值为有序序列，而从下标1到末尾的元素temp构成无序序列
3. temp和前面的有序序列进行依次比较，比较的同时也让有序序列往后移动，直到找到比temp大的元素，就找到要插入的位置。

function insertSort(arr){
    //是否是数组
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
        //数组是否为空
        var len=arr.length;
        if(len === 0){
            return arr;
        }
        //认为第1个数是有序的，从第2个数开始遍历,下标从1开始
        for(var i=1;i<len;i++){
            //取出第i个数，和前i-1个数比较后，插入合适的位置
            temp=arr[i];
            //因为前i-1个数都是升序序列
            //则当比较的数arr[j]比temp大，就要后移
            var j = i - 1;
            while(j>=0 && arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            //插入的位置,j+1则是因为while循环往回退多了一位
            arr[j+1]=temp;
        }
        return arr;
    }else{
        return 'not an Array!'
    }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));

• 时间复杂度为\(O(N^2)\)
• 空间复杂度为\(O(1)\)

插入排序是稳定算法

通过二分查找搜索插入的位置

/* 
二分查找函数
array:输入的完整数组
n:有序序列的长度
value:待插入的元素
*/
function BinarySearch(array,n,value){
    //有序序列的左右双指针
    let left=0,right=n-1,mid;
    //采用闭区间的写法
    while(left<=right){
        //取中间下标，做二分查找判断
        mid = left + ((right-left)>>1);
        if(array[mid]>value){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    //防止出现单个元素的情况出现
    return (left<n) ? left : -1;
}

//二分插入排序
function BinaryInsertSort(arr){
    //判断是否是数组
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array'){
        if(arr.length === 0){
            return arr;
        }
        for(var i=1;i<arr.length;i++){
            var insert_index=BinarySearch(arr,i,arr[i]);
            //经过判断插入元素的位置没有问题后
            if(insert_index !== -1){
                var temp = arr[i];
                var j = i-1;
                //往后移动
                while(j >= insert_index){
                    arr[j+1]=arr[j];
                    j--;
                }
                //插入的位置 arr[insert_index]也行
                arr[j+1]=temp;
            }
        }
        return arr;
    }else{
        return 'not an Array!'
    }
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(BinaryInsertSort(arr));