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對程式碼的效能進行測試分析，結果請猛擊這裡.
