js归并排序-快速排序-堆排序

前端面试经常遇到一个问题：有两个无序数组，用一个方法把他们合并且排序，嗯嗯，那么就concat然后归并吧

 function merge(left, right){
        let tmp = [];
        while(left.length && right.length){
            if(Number.parseInt(left[0])<Number.parseInt(right[0])){
                tmp.push(left.shift());
            }else{
                tmp.push(right.shift());
            }
            console.log(tmp.join(',')+'...'+left.join(',')+'...'+right.join(','));
        }
        return tmp.concat(left,right);
    }
function mergesort(arr){
        console.log('mergesort--'+arr);
        if(arr.length==1){
            return arr;
        }else{
            let mid = Math.floor(arr.length/2);
            let left = arr.slice(0, mid);
            let right = arr.slice(mid);
            console.log('hihi'+left.join(',')+'--'+right.join(','));
            return merge(mergesort(left),mergesort(right));
        }
    };
function star(){
            var arr1 = document.getElementsByTagName('input')[0].value.split(',');
        var arr2 = document.getElementsByTagName('input')[1].value.split(',');
        var ele = document.getElementsByTagName('span')[0];
            console.log('start'+arr1+arr2);
        ele.innerHTML = mergesort(arr1.concat(arr2)).toString();
    }

能不用冒泡和插入排序尽量就不用了，因为复杂度都是n方，归并和快速都是nlogn，相对好一些
下面任然介绍一下快排：

function quicksort(arr){
        if(arr.length<=1) return arr;
        let judge = 0,left = [], right = [];
        judge = arr[Math.floor(arr.length/2)];
        arr.splice(Math.floor(arr.length/2),1);
        for(let i = 0; i<arr.length; i++){
            console.log(typeof arr[i]);
            if(arr[i]<judge){
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
            console.log(left.concat([judge],right).toString());
        }
        return quicksort(left).concat([judge],quicksort(right));
    };
 function star(){
            var arr1 = document.getElementsByTagName('input')[0].value.split(',');
        var arr2 = document.getElementsByTagName('input')[1].value.split(',');
        arr1 = arr1.map(x=>+x);
        arr2 = arr2.map(x=>+x);
        var ele = document.getElementsByTagName('span')[0];
            console.log('start'+arr1+arr2);
        ele.innerHTML = quicksort(arr1.concat(arr2)).toString();
    }

提示：如果快速排序不把judge标志元素从数组中splice掉，会导致栈溢出
最后是堆排序，利用大顶堆进行1）构造堆 2）调整堆

function heap(arr, large, len) {
    var origin = large;
    var left = large*2 + 1;
    var right = left + 1;
    var temp = null;
    if(left<len && arr[large]<arr[left]){
        large = left;
    }
    if(right<len && arr[large]<arr[right]){
        large = right;
    }
    if(large !== origin) {
        temp = arr[origin];
        arr[origin] = arr[large];
        arr[large] = temp;
        arguments.callee(arr, large, len);
    }
    return arr;
}
function sort(arr) {
    var len = arr.length;
    var temp = null;
    var res = [];
    //init
    for(let i = Math.floor(len/2); i>=0;i--) {
        heap(arr, i, len);
console.log(arr,'666')
    }
    for(let i = len-1;i>0;i--) {
        res.push(arr);
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heap(arr, 0, i);
    }
    return arr;
}
sort([0,4,5,6,2,21,3,5,9])