js有序數(shù)組的連接問題

2019-11-20 21:55:37

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

1.前言

昨天碰到一道關(guān)于如何解決有序數(shù)組的連接問題，這是一個(gè)很常見的問題。但是這里要考慮到代碼的效率問題，因?yàn)橐B接的數(shù)組都是有序的，這是一個(gè)非常重要的前提條件。

2.簡(jiǎn)單但效率不高的算法

我首先想到的是使用內(nèi)置的concat方法，然后再對(duì)其進(jìn)行排序，這種方法完全沒有考慮到數(shù)組是有序的前提條件，代碼如下：

復(fù)制代碼代碼如下:

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

　　為了弄清楚sort排序到底使用的是什么算法，特地到看了V8引擎的算法（連接），大概意思是當(dāng)數(shù)組的長(zhǎng)度較短的時(shí)候使用的是插入排序（InsertionSort），當(dāng)數(shù)組的長(zhǎng)度較長(zhǎng)的時(shí)候使用的是快速排序（QuickSort）。糾正了自己長(zhǎng)時(shí)間來的一個(gè)誤區(qū)，一直以為sort使用的是冒泡。

3. 取小值插入的方法

大概思路：就是同時(shí)對(duì)兩個(gè)數(shù)組進(jìn)行遍歷，設(shè)置兩個(gè)標(biāo)志（i，j）用于記錄遍歷的位置，將兩個(gè)數(shù)組中較小的那個(gè)值插入新數(shù)組中，接著再將標(biāo)志往前移動(dòng)一個(gè)位置，重復(fù)比較，直到搜索值都插入到數(shù)組中。第一次做的時(shí)候判斷條件寫錯(cuò)了，所以出現(xiàn)了死循環(huán)，暴露了自己算法能力還是挺薄弱的。

復(fù)制代碼代碼如下:

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] 

　　將這個(gè)算法與上面的方法1，在jsperf進(jìn)行性能對(duì)比，發(fā)現(xiàn)第二種算法的效率明顯優(yōu)于第一種。不相信就猛擊這里。

4.問題升級(jí)：增加合并數(shù)組的數(shù)量

假如增加數(shù)組的個(gè)數(shù)，；例如 A = [1,5],B = [2,6],C = [3,4].......K = [....]，求合并的數(shù)組。

當(dāng)時(shí)被問到這個(gè)問題，第一感覺就是很像”歸并算法“，但是又一想使用歸并算法是用不上數(shù)組有序這個(gè)前提條件的。接著又想到了堆排序、快排序等算法，發(fā)現(xiàn)就是無法很有效地用上數(shù)組有序這個(gè)前提條件，最后選擇放棄。面試完后依然沒有思路，想了好久不知道如何高效的解決這個(gè)問題。快回宿舍的時(shí)候，師弟說了一句”又要過節(jié)了“，”又“字點(diǎn)醒了我，代碼如下：

復(fù)制代碼代碼如下:

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] 