몇 가지 일반적인 Java 버블 정렬 알고리즘: 오름차순으로 정렬

Java 버블 정렬: 작은 것부터 큰 것까지 몇 가지 일반적인 작성 방법, 구체적인 코드 예제가 필요함

버블 정렬은 두 개의 인접한 요소를 반복적으로 비교하고 크기에 따라 정렬하는 간단한 정렬 알고리즘입니다. 전체 시퀀스가 ​​될 때까지 Swap이 수행됩니다. 순서대로입니다. Java에는 버블 정렬을 위한 몇 가지 일반적인 작성 방법과 최적화 방법이 있습니다. 다음은 다섯 가지 일반적인 작성 방법을 소개하고 구체적인 코드 예제를 제공합니다.

첫 번째 작성 방법: 일반 버블 정렬

일반 버블 정렬은 두 가지 수준의 루프를 직접 중첩합니다. 외부 루프는 비교 라운드 수를 제어하고 내부 루프는 특정 비교 및 ​​교환을 수행합니다.

public static void bubbleSort1(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

두 번째 작성 방법: 외부 루프 최적화

첫 번째 작성 방법을 기준으로 한 번의 정렬에서 교환이 수행되지 않으면 배열이 이미 순서대로 정렬되어 정렬이 조기에 종료될 수 있음을 의미합니다. . 이러한 최적화를 달성하기 위해 스왑이 발생했는지 기록하는 플래그 비트를 추가할 수 있습니다.

public static void bubbleSort2(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

세 번째 작성 방법: 내부 루프 최적화

두 번째 작성 방법을 기반으로 하면 각 비교 라운드가 가장 큰 요소를 끝까지 "버블링"한다는 것을 알 수 있습니다. 따라서 라운드당 내부 루프 비교 횟수를 점차적으로 줄일 수 있습니다.

public static void bubbleSort3(int[] arr) {
    int n = arr.length;
    int lastSwapIndex;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        i = n - lastSwapIndex - 2;
    }
}

네 번째 작성 방법: 내부 및 외부 루프 최적화

세 번째 작성 방법에 따르면, 특정 비교 라운드에서 배열이 교환되지 않으면 배열 뒤의 요소가 이미 순서대로 되어 있다는 의미입니다. , 정렬이 조기 종료될 수 있습니다.

public static void bubbleSort4(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, rightBoundary;
    rightBoundary = n - 1;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        if (rightBoundary <= 1) {
            break;
        }
    }
}

다섯 번째 작성 방법: 외부 루프와 내부 루프 최적화

네 번째 작성 방법을 기반으로 각 비교 라운드에서 현재 라운드의 가장 큰 요소를 찾아서 올바른 위치에 배치한다는 것을 알 수 있습니다. 위치 . 따라서 각 비교 라운드에서 최대값과 최소값을 모두 찾아서 정렬할 수 있습니다.

public static void bubbleSort5(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, leftBoundary, rightBoundary;
    leftBoundary = 0;
    rightBoundary = n - 1;
    while (leftBoundary < rightBoundary) {
        lastSwapIndex = 0;
        for (int j = leftBoundary; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        for (int j = rightBoundary; j > leftBoundary; j--) {
            if (arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                lastSwapIndex = j - 1;
            }
        }
        leftBoundary = lastSwapIndex;
    }
}

위는 버블 정렬의 다섯 가지 일반적인 작성 방법입니다. 각 작성 방법에는 서로 다른 최적화 방법이 있으며, 실제 사용에서는 특정 상황에 따라 적절한 작성 방법을 선택할 수 있습니다. 이러한 최적화를 통해 버블 정렬의 효율성을 높이고 정렬 시간을 단축할 수 있습니다.

버블 정렬은 간단하지만, 대용량 데이터를 정렬할 때는 성능이 좋지 않습니다. 따라서 실제 응용에서는 퀵 정렬, 병합 정렬 등과 ​​같은 보다 효율적인 정렬 알고리즘이 더 일반적으로 사용됩니다.

위 내용은 몇 가지 일반적인 Java 버블 정렬 알고리즘: 오름차순으로 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!