JavaScript 버블 정렬 알고리즘

버블 정렬을 통한 정렬 알고리즘은 상대적으로 간단하고 이해하기 쉽기 때문에 사람들이 가장 먼저 생각하는 정렬 알고리즘입니다. 기본 아이디어는 두 숫자를 동시에 비교하여 다른 항목으로 넘어가기 전에 숫자가 올바른 순서인지 확인하는 것입니다. 각 레벨이 끝나면 귀중한 항목이 올바른 위치로 "정렬"되어 궁극적으로 다른 항목만 정렬됩니다. 원본 텍스트: http://caibaojian.com/javascript-bubble-sort.html

알고리즘 구현 아이디어

첫 번째 항목과 두 번째 항목 비교

첫 번째 경우 항목이 두 번째 항목 뒤에 있어야 합니다.

두 번째 항목과 세 번째 항목을 비교

두 번째 항목이 세 번째 항목 뒤에 있어야 하면 서로 바꿉니다

데이터 끝

이 과정은 데이터가 완전히 정렬될 때까지 여러 번 반복됩니다. 매번 마지막 항목이 올바르게 정렬되므로 정렬할 항목이 점점 줄어듭니다. 이해를 돕기 위해 배열을 비교해 보겠습니다: [3, 2, 4, 5, 1].

비교 과정 예시

첫 번째는 첫 번째 항목과 두 번째 항목을 비교하는 긍정 정렬입니다. 항목, 2가 3보다 작으므로 3이 마지막에 순위가 지정되고 결과는 [2,3,4,5,1]입니다.

두 번째와 세 번째 항목의 순서가 정확하므로 필요하지 않습니다. 교환; 세 번째와 네 번째 항목도 정확하므로 교환할 필요가 없습니다. 네 번째와 다섯 번째 항목이 교환되며 결과는 [2,3,4,1,5]입니다.

첫 번째 항목을 다시 반복합니다. 그리고 두 번째 아이템은 차례로 세 번째와 네 번째 아이템을 교환하여 [2,3,1,4,5]

세 번째 사이클에서는 두 번째와 세 번째 아이템을 [2,1]로 교환합니다. ,3,4,5]

네 번째 사이클에서는 첫 번째와 두 번째 교환은 [1,2,3,4,5]

버블 정렬을 구현하는 첫 번째 단계입니다. 배열의 두 항목을 교환하는 방법을 만듭니다. 이 방법은 많은 비효율적인 정렬에서 비교적 일반적입니다. 간단한 자바스크립트 구현 코드는 다음과 같습니다.

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

via 위에서 언급했듯이 이 정렬 알고리즘은 여러 정렬이 필요하기 때문에 상대적으로 비효율적입니다. 배열에 n개의 항목이 있다고 가정하면 계산하는 데 2의 n제곱이 필요합니다. http://caibaojian.com/javascript-bubble-sort.html

Positive Directional 버블링 알고리즘

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

via 외부 루프는 루프 주기 수를 제어하고 내부 루프는 항목 간의 정렬 비교입니다.

Reverse Bubble Sort

function bubbleSort(items){
    var len = items.length,
        i, j;

    for (i=len-1; i >= 0; i--){
        for (j=len-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                swap(items, j, j-1);
            }
        }
    }

    return items;
}

via 위 두 코드의 결과는 동일하며 작은 것부터 큰 것까지 정렬되지만 루프의 순서는 약간 다릅니다. 둘 다 긍정적인 순서 거품 거품입니다.

역 버블 정렬

사실 첫 번째 항목이 두 번째 항목보다 작을 때 위치를 바꾸는 등의 크기 변경을 판단하는 것입니다.

function bubbleSort2(items){
var len = items.length,
i,j,stop;
for(i=0;i<len; i++){
for(j=0,stop=len-i;j<stop;j++){
if(items[j]<items[j+1]){
swap(items,j,j+1);
}
}
}
return items;
}

요약

을 통해 다시 한번 말하지만, 버블 정렬은 알고리즘을 이해하고 추가 정보를 제공하는 데 도움이 되는 간단한 도구일 뿐입니다. 더 많은 지식을 얻으려면. 우리가 가장 많이 사용하는 것은 아마도 내장된 Array.prototype.sort() 프로토타입 메소드일 것입니다. 그것이 더 효율적이기 때문입니다.

JavaScript 버블 정렬 알고리즘과 관련된 더 많은 글은 PHP 중국어 홈페이지를 주목해주세요!