JavaScript 有序数组高效合并算法解析

前言

前言

在处理日常开发任务时，常遇到需要合并两个已排序数组的场景。由于输入数据本身具有有序性，这一前提条件成为优化算法效率的关键切入点。

简单但效率不高的算法

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

初学者往往首先想到利用JavaScript内置的concat方法连接数组，随后调用sort方法进行排序。这种方案完全忽略了数组已有序的前提，导致不必要的计算开销。

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

为了探究sort方法的底层实现，查阅V8引擎源码发现：当数组长度较短时采用插入排序（InsertionSort），长度较长时则切换为快速排序（QuickSort）。这纠正了以往认为sort仅使用冒泡排序的误解。

取小值插入的方法

3. 取小值插入的方法

核心思路是利用双指针同时遍历两个数组，通过比较当前指针所指元素的大小，将较小值放入结果数组，并移动对应指针。该过程重复直至所有元素处理完毕。初次实现时因判断条件疏漏导致死循环，反映出算法逻辑严谨性的重要性。

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]

问题升级：增加合并数组的数量

通过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对代码的性能进行测试分析，结果请猛击这里.