一般的な Java バブル ソート アルゴリズム: 昇順でソート

Java バブル ソート: 小規模なものから大規模なものまで、いくつかの一般的な記述方法、具体的なコード例が必要です

バブル ソートは、隣接する 2 つの要素を繰り返し比較する単純なソート アルゴリズムです。シーケンス全体が順序付けされるまで、サイズ順序に従ってそれらを交換します。 Javaではバブルソートの一般的な記述方法や最適化方法がいくつかありますが、ここでは一般的な5つの記述方法と具体的なコード例を紹介します。

最初の書き方: 通常のバブル ソート

通常のバブル ソートは 2 レベルのループを直接ネストします。外側のループは比較のラウンド数を制御し、内側のループは特定の比較を実行します。そして交換します。

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;
            }
        }
    }
}

2 番目の書き方: 外側のループの最適化

1 番目の書き方に基づいて、1 回のソートで交換が行われない場合は、配列がすでに格納されていることを意味します。ご注文及び仕分けは早期に終了する場合がございます。この最適化を実現するには、スワップが発生したかどうかを記録するフラグ ビットを追加します。

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;
        }
    }
}

3 番目の記述方法: 内部ループの最適化

2 番目の記述方法に基づくと、比較の各ラウンドで最大の要素が最後まで「バブル」されることがわかります。したがって、ラウンドあたりの内部ループの比較の数を徐々に減らすことができます。

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;
    }
}

4 番目の記述方法: 内部ループと外部ループの最適化

3 番目の記述方法に基づいて、特定のラウンドの比較で配列が交換されない場合は、配列の背後にある要素はすでに順序が整っているため、ソートを早期に終了できます。

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;
        }
    }
}

5 番目の書き方: 外側のループと内側のループの最適化

4 番目の書き方に基づくと、各ラウンドの比較で最大の要素が見つかることがわかります。現在のラウンドを正しい場所に置きます。したがって、比較の各ラウンドで最大値と最小値の両方を見つけて並べ替えることができます。

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;
    }
}

上記はバブルソートの一般的な記述方法を5つ挙げましたが、それぞれの記述方法で最適化方法が異なるため、実際に使用する場合は状況に応じて適切な記述方法を選択してください。これらの最適化により、バブルソーティングの効率が向上し、ソーティング時間を短縮できます。

バブル ソートは単純ですが、大規模なデータをソートする場合はパフォーマンスが低下します。したがって、実際のアプリケーションでは、クイック ソート、マージ ソートなどのより効率的なソート アルゴリズムがより一般的に使用されます。

以上が一般的な Java バブル ソート アルゴリズム: 昇順でソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。