js 정렬 배열 연결 문제_javascript 기술

1. 머리말

어제 정렬된 배열의 연결 문제를 해결하는 방법에 대한 문제가 발생했습니다. 이는 매우 일반적인 문제입니다. 하지만 여기서는 코드의 효율성을 고려해야 합니다. 연결될 어레이가 모두 순서대로 정렬되어 있기 때문에 이는 매우 중요한 전제 조건입니다.

2. 단순하지만 비효율적인 알고리즘

제가 가장 먼저 생각한 것은 내장된 concat 방법을 사용한 후 정렬하는 것이었습니다. 이 방법은 배열 순서라는 전제 조건을 고려하지 않습니다.

코드 복사 코드는 다음과 같습니다.

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

정렬에 어떤 알고리즘이 사용되는지 알아보기 위해 특별히 V8 엔진의 알고리즘(Connection)을 살펴보았는데, 이는 아마도 배열의 길이가 짧을 경우 삽입 정렬이 된다는 의미일 것입니다. InsertionSort)를 사용하며, 배열의 길이가 긴 경우에는 Quick Sort(QuickSort)를 사용합니다. 나는 오랫동안 그런 종류의 버블링을 사용한다고 생각했던 오해를 바로잡았습니다.

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



jsperf에서 위의 방법 1과 이 알고리즘의 성능을 비교해 보면 두 번째 알고리즘의 효율성이 첫 번째 알고리즘보다 훨씬 더 우수하다는 것을 알 수 있습니다. 믿을 수 없다면
여기
를 누르세요.

4. 문제 업그레이드: 병합된 배열 수를 늘립니다.

배열 수를 늘리면, 예를 들어 A = [1,5], B = [2,6] , C = [ 3,4]....K = [....], 병합된 배열을 찾습니다. 
이 질문을 받았을 때 첫인상은 "병합 알고리즘"과 매우 유사하다는 것이었지만, 병합 알고리즘을 사용하려면 배열이 정렬되는 전제 조건이 필요하지 않습니다. 그러다가 힙 정렬, 퀵 정렬 등의 알고리즘을 생각해 보았지만 배열 순서의 전제 조건을 효과적으로 사용할 수 없다는 것을 발견하고 결국 포기했습니다. 인터뷰 후에도 저는 오랫동안 고민했고 이 문제를 효율적으로 해결하는 방법을 몰랐습니다. 기숙사로 돌아가려는데 후배가 "또 휴일이구나"라며 나를 깨웠다. 코드는 다음과 같다.

코드 복사

코드는 다음과 같습니다.

function conMore(){
    var externalArr = [], i ,len = 인수.길이 , 결과 = [];
    for(i = 0 ; i        externalArr.push(arguments[i]);
    }
    if(result.length === 0){
        result = externalArr[0];
    }
    for(i=1 ;i< len; i ){
        result = con(result,outerArr[i]);
    }
    결과 반환;
}
함수 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 ]);
       }
   }
   결과 반환;
}
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对代码的性能进行测试分析,结果请猛击这里.

성명：

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.