js ordered array connection problem_javascript skills

1. Foreword

Yesterday I encountered a problem about how to solve the connection problem of ordered arrays. This is a very common problem. But the efficiency of the code must be taken into consideration here, because the arrays to be connected are all ordered, which is a very important prerequisite.

2. Simple but inefficient algorithm

The first thing I thought of was to use the built-in concat method and then sort it. This method does not take into account the prerequisite that the array is ordered. The code is as follows:

Copy code The code is as follows:

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

In order to figure out what algorithm is used for sorting, I specifically looked at the algorithm of the V8 engine (Connection), which probably means that when the length of the array is short, insertion sort is used ( InsertionSort), when the length of the array is long, quick sort (QuickSort) is used. I corrected a misunderstanding I had for a long time. I always thought that sort used bubbling.

3. Method of inserting small values ​​

The general idea is to traverse two arrays at the same time, set two flags (i, j) to record the traversed position, insert the smaller value of the two arrays into the new array, and then set the flag Move forward one position and repeat the comparison until the search values ​​are inserted into the array. The first time I did it, I wrote the wrong judgment conditions, so an infinite loop occurred, which exposed my own algorithmic capabilities.       

Copy code The code is as follows:

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]); [3,5,6,7,10];
console.log(con(a,b)); //[1,2,3,4,5,6,7,10]



Comparing the performance of this algorithm with method 1 above in jsperf, we found that the efficiency of the second algorithm is significantly better than the first one. If you don’t believe it, hit
here
.

4. Upgrade the problem: increase the number of merged arrays

If you increase the number of arrays, for example, A = [1,5], B = [2,6], C = [ 3,4]....K = [....], find the merged array. 
When I was asked this question, my first impression was that it was very similar to the "merge algorithm", but if you want to use the merge algorithm, you don't need the prerequisite that the array is ordered. Then I thought about algorithms such as heap sort and quick sort, but found that the prerequisite of array ordering could not be used effectively, and finally gave up. After the interview, I still had no idea. I thought for a long time and didn’t know how to solve this problem efficiently. When I was about to return to the dormitory, my junior brother said "It's another holiday" and "" woke me up. The code is as follows:

Copy code

The code is as follows:

function conMore(){
    var outerArr = [], i ,len = arguments.length , result = [];
    for(i = 0 ; 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对代码的性能进行测试分析，结果请猛击这里.

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn