javascript 에서 흔히 볼 수 있 는 간단 한 알고리즘 문제

1. 피 보 나치 수열 (1, 1, 2, 3, 5, 8, 13, 21...)
가장 간단 한 실현

function f1(n){
    // i++;     //      
    if(n <= 2) return 1;
    return f1(n-1) + f1(n-2);
}

이것 은 가장 간단 한 실현 이지 만, 우 리 는 재 귀 횟수 가 많아 서 메모리 가 매우 소모 되 고, 성능 에 항상 좋 지 않다 는 것 을 안다.그래서 다른 방법 으로 할 수 있어 요.

function f2(n){
    var cache = [1,1,1];
    function _fn(n){
        // i++;     //      
        if(cache[n]) return cache[n];
        cache[n-1] = _fn(n-1);
        cache[n-2] = _fn(n-2);
        return cache[n-1] + cache[n-2];
    }
    return _fn(n);
}

이 방법 은 주로 가 져 온 값 캐 시 (여 기 는 하나의 배열 로) 를 올 려 서 이 값 을 읽 을 때 캐 시 에서 직접 가 져 오 면 되 고 일부 재 귀 를 줄 일 수 있 습 니 다.상기 두 가지 방법 은 들 어 오 는 n 수치 가 작 을 때 괜 찮 습 니 다. n 의 값 이 조금 만 크 면 첫 번 째 방법 은 바로 무 너 집 니 다.다음은 이들 의 집행 성능 상의 차이 이다. n = 40 시

console.log(f1(40), i, Date.now()-t)    //  102334155，    204668309，  2112ms
console.log(f2(40), i, Date.now()-t)    //  102334155，    77，  7ms

 
2. 이분법 찾기
원 리 는 한 단락 의 범위 내 에서 중간 위치의 값 과 찾 으 려 는 값 을 비교 한 다음 에 점차적으로 범 위 를 좁 히 는 것 이다.전제조건 은 배열 이 순서대로 배열 되 어 있다.
아래 코드 는 기본 배열 이 정렬 되 어 있 습 니 다.

/**
 * @param {[]} arr   
 * @param {number} x      
 * @method                （    ）
 */
function bsearch(arr, x){
    var l = 0;              //    
    var r = arr.length - 1;     //    
    var guess = 0;          //    

    while(l <= r){
        //      
        guess = Math.floor((r + l) / 2);
        //          
        if(arr[guess] === x) return guess;
        //             ，       
        else if(arr[guess] > x) r = guess - 1;
        //             ，       
        else l = guess + 1;
    }
    //     
    return -1;
}

var arr = [1,2,3,34,55,56,89,102,233,345,699,785];
console.log(bsearch(arr, 11))       //-1
console.log(bsearch(arr, 111))      //-1
console.log(bsearch(arr, 345))      //9
console.log(bsearch(arr, 102))      //7

 
3. 배열 정렬
거품 정렬
사고: 여기 서 예 를 들 어 정렬 하고 배열 에서 인접 한 두 가지 값 을 비교 합 니 다. 만약 에 앞의 것 이 뒤의 것 보다 크 면 교환 위 치 는 한 바퀴 가 비교 하면 최대 치 를 맨 뒤에 얻 을 수 있 고 나머지 는 이렇게 순환 적 으로 비교 할 수 있 습 니 다.

/**
 * @param {array} arr       
 * @method       
 * @return {array}       
 */
function bubbleSort(arr){
    //          
    for(var i=0; i arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

var arr = [1,3,23,54,-9,6,10,99];
console.log(bubbleSort(arr))    //[ -9, 1, 3, 6, 10, 23, 54, 99 ]

정렬 선택
원리: 사실 거품 정렬 과 차이 가 많 지 않 습 니 다. 거품 정렬 은 두 가지 가 서로 바 뀌 지만 정렬 을 선택 하 는 것 은 현재 배열 의 정렬 되 지 않 은 부분 에서 그 최대 치 를 선택 한 다음 에 이 부분의 마지막 으로 이동 하 는 것 입 니 다.예 를 들 어 현재 배열 의 길 이 는 5 이 고 처음으로 이 5 개 중에서 최대 치 를 찾 아 마지막 으로 이동 한 다음 에 나머지 4 개 를 찾 아 최대 치 를 찾 아 이 4 개의 마지막 으로 이동 합 니 다. 이렇게 순환 하면 배열 이 마지막 1 개 만 남 을 때 까지 배열 정렬 후의 첫 번 째 입 니 다.

/**
 * @param {array} arr   
 * @param {number} length     
 * @method             
 * @return          
 */
function findMax(arr, length){
    var max = arr[0], index = 0;
    for(var i=1; i= max) {
            max = arr[i];
            index = i;
        }
    }
    return index;
}

/**
 * @param {array} arr       
 * @param {number} length   length
 * @method     
 * @return {array}        
 */
function selectSort(arr, length){
    //           ，          
    while(length > 1){
        //                 
        var index = findMax(arr, length);
        var temp = arr[index];
        //                  
        arr[index] = arr[length-1];
        arr[length-1] = temp;
        length--;
    }
    return arr;
}

var arr = [11,22,23,-9,-23,11,16,23,-9,11,23,56,22];
console.log(selectSort(arr, arr.length));       //[ -23, -9, -9, 11, 11, 11, 16, 22, 22, 23, 23, 23, 56 ]

빠 른 정렬
사고: 두 개의 빈 배열 l 과 r 를 만 들 고 정렬 할 배열 에서 중간 위치 에 있 는 값 centerValue 를 꺼 낸 다음 에 배열 을 옮 겨 다 니 며 현재 값 이 centerValue 보다 작 으 면 l 배열 에 추가 합 니 다. 그렇지 않 으 면 r 배열 에 추가 하고 마지막 으로 배열 은 l, centerValue, r 를 합 쳐 되 돌려 줍 니 다.그리고 함수 재 귀 를 진행 합 니 다.

/**
 * @param {array} arr       
 * @method       
 * @return {array}       
 */
function quickSort(arr){
    //         length=1 ，      
    if(arr.length < 2) return arr;
    var l = [], r = [];
    //     
    var centerIndex = Math.floor((arr.length - 1)/2);
    //         
    var centerValue = arr.splice(centerIndex, 1)[0];
    for(var i=0; i

몇 가지 정렬 효율 비교
정렬 을 선택 하면 거품 정렬 과 비슷 합 니 다.
먼저 length 가 100 인 수치 배열 을 무 작위 로 생 성 합 니 다. 거품 정렬, 빠 른 정렬, 원생 sort 는 차이 가 많 지 않 고 5 ~ 7ms 정도 입 니 다.
length 는 1000 의 수치 배열 로 원생 sort 는 약간 조각 이 있 고 거품 이 나 는 것 과 빠 른 정렬 은 차이 가 많 지 않 습 니 다.
length 는 10000 의 수치 배열 로 원생 sort 와 빠 른 정렬 은 차이 가 별로 없 으 며 약 20 ~ 30ms 로 거품 정렬 이 가장 느 리 고 100 여 ms 가 필요 합 니 다.
length 는 100000 의 수치 배열 로 원생 sort 가 가장 빠 르 고 100 ms 정도 입 니 다.빠 른 정렬 순서, 200 여 ms;거품 정렬 이 가장 느 리 고 10s 정도 (차이 가 매우 크다).
변태 가 왔 습 니 다. 마지막 에 length 는 1000000 에 왔 습 니 다. 원생 이 가장 빠 르 고 800 ms 정도 입 니 다.빠 른 정렬 순서, 3s 정도;거품 정렬 이 바로 튀 었 다.
상기 구체 적 인 시간 수 치 는 기계 환경의 영향 을 많이 받 을 수 있 고 비교 만 할 수 있 으 며 실제 수 치 를 대표 하 는 것 이 아니다.