1.前言
昨天碰到一道關於如何解決有序數組的連接問題，這是一個很常見的問題。但是這裡要考慮到代碼的效率問題，因為要連接的數組都是有序的，這是一個非常重要的前提條件。
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對代碼的性能進行測試分析，結果請猛擊這裡.