js有序數組的連接問題_javascript技巧

1.前言 

昨天碰到一道關於如何解決有序數組的連接問題，這是一個很常見的問題。但這裡要考慮到程式碼的效率問題，因為要連接的陣列都是有序的，這是一個非常重要的前提條件。

2.簡單但效率不高的演算法 

 我首先想到的是使用內建的concat方法，然後再對其進行排序，這種方法完全沒有考慮到數組是有序的前提條件，代碼如下：    

複製程式碼 程式碼如下:

f arrA.concat(arrB).sort();
}

　　為了弄清楚sort排序到底使用的是什麼演算法，特地到看了V8引擎的演算法（

連接），大概意思是當數組的長度較短的時候使用的是插入排序（ InsertionSort），當陣列的長度較長的時候使用的是快速排序（QuickSort）。修正了自己長時間來的一個誤區，一直以為sort使用的是冒泡。

3. 取小值插入的方法 

 大概思路：就是同時對兩個數組進行遍歷，設定兩個標誌（i，j）用於記錄遍歷的位置，將兩個數組中較小的那個值插入新數組中，接著再將標誌往前移動一個位置，重複比較，直到搜尋值都插入陣列。第一次做的時候判斷條件寫錯了，所以出現了死循環，暴露了自己演算法能力還是挺薄弱的。     

複製程式碼 程式碼如下:

function con(arrA,arrB){
 i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA lenB,result = [];
   for(i=0,j=0,k =0; k        if(i = lenB || arrA[i]        🎜>            result.push(arrB[j ]);
        }
   }
  ,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 outArr = [], i ,len = argument.length , result = [];
    for(i = 0 ; i        externalArr.push(arguments[i]);
    }
    if(result.length === 0){
        result = outArr[0];
    }
    for(i=1 ;i        結果 = con(結果,outerArr[i]);
    }
    回傳結果；
}
function con(arrA,arrB){
   var i , j , k, lenA = arrA.lenghth, lenB = var i , j , k, lenA = arrA.lengarrth, lenB = lenB，結果= []；
   for(i=0,j=0,k =0; k        if(i = lenB || arrA[i]            效果.push(arrA[i ]); 
       }else{
            result.push(arrB[j ]);
       }
   }
   回傳結果；
}
var a = [1,4,7], b = [2,5,8], c = [3,6,99 ,10];
console.log(conMore(a,b,c));   //[1,2,3,4,5,6,7,8,9,10]

再次使用jsperf對程式碼的效能進行測試分析，結果請猛擊這裡.