js有序数组的连接问题

昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题。但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件。

2.简单但效率不高的算法 

我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下:    

复制代码 代码如下:


function concatSort(arrA,arrB){
     return arrA.concat(arrB).sort();
}

  为了弄清楚sort排序到底使用的是什么算法,特地到看了V8引擎的算法(连接),大概意思是当数组的长度较短的时候使用的是插入排序(InsertionSort),当数组的长度较长的时候使用的是快速排序(QuickSort)。纠正了自己长时间来的一个误区,一直以为sort使用的是冒泡。

3. 取小值插入的方法 

大概思路:就是同时对两个数组进行遍历,设置两个标志(i,j)用于记录遍历的位置,将两个数组中较小的那个值插入新数组中,接着再将标志往前移动一个位置,重复比较,直到搜索值都插入到数组中。第一次做的时候判断条件写错了,所以出现了死循环,暴露了自己算法能力还是挺薄弱的。     

复制代码 代码如下:


function con(arrA,arrB){
   var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA + lenB,result = [];
   for(i=0,j=0,k =0; k < allLen; k++ ){
       if(i < lenA &&(j >= lenB || arrA[i] < arrB[j])){
           result.push(arrA[i++]); 
       }else{
            result.push(arrB[j++]);
       }
   }
   return result;
}
var a = [1,2,4], b = [3,5,6,7,10];
console.log(con(a,b));  //[1,2,3,4,5,6,7,10]

  将这个算法与上面的方法1,在jsperf进行性能对比,发现第二种算法的效率明显优于第一种。不相信就猛击这里

4.问题升级:增加合并数组的数量

  假如增加数组的个数,;例如 A = [1,5],B = [2,6],C = [3,4].......K = [....],求合并的数组。   

当时被问到这个问题,第一感觉就是很像”归并算法“,但是又一想使用归并算法是用不上数组有序这个前提条件的。接着又想到了堆排序、快排序等算法,发现就是无法很有效地用上数组有序这个前提条件,最后选择放弃。面试完后依然没有思路,想了好久不知道如何高效的解决这个问题。快回宿舍的时候,师弟说了一句”又要过节了“,”又“字点醒了我,代码如下:   

复制代码 代码如下:


function conMore(){
    var outerArr = [], i ,len = arguments.length , result = [];
    for(i = 0 ; i<len; i++){
        outerArr.push(arguments[i]);
    }
    if(result.length === 0){
        result = outerArr[0];
    }
    for(i=1 ;i< len; i++){
        result = con(result,outerArr[i]);
    }
    return result;
}
function con(arrA,arrB){
   var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA + lenB,result = [];
   for(i=0,j=0,k =0; k < allLen; k++ ){
       if(i < lenA &&(j >= lenB || arrA[i] < arrB[j])){
           result.push(arrA[i++]); 
       }else{
            result.push(arrB[j++]);
       }
   }
   return result;
}
var a = [1,4,7], b = [2,5,8], c = [3,6,9,10];
console.log(conMore(a,b,c));   //[1,2,3,4,5,6,7,8,9,10]

再次使用jsperf对代码的性能进行测试分析,结果请猛击这里.

您可能感兴趣的文章:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wdzdfg.html