Javaバブルソートの一般的な書き方と分析を学ぶ-＆＃＆チュートリアル-php.cn

Javaバブルソートの一般的な書き方と分析を学ぶ

WBOY

リリース： 2024-01-09 12:02:00

オリジナル

928 人が閲覧しました

Javaバブルソートの一般的な書き方と分析を学ぶ

Java バブルソートを素早くマスターする: いくつかの一般的な記述方法の分析

コンピューターサイエンスにおいて、バブルソートは単純ですが非効率な並べ替えアルゴリズムです。基本的な考え方は、隣接する要素を複数回比較して交換することで、より大きな要素を配列の最後まで徐々に「バブル」させることです。

この記事では、いくつかの一般的な Java バブルソート方法を紹介し、読者がこのソートアルゴリズムをすぐに習得できるように具体的なコード例を示します。

バブルソートの基本的な書き方

バブルソートの基本的な書き方は非常に簡単で、ネストされたループを使用して、隣接する要素を交換し、1 つずつ比較します。 . 要素を配列内に配置し、より大きな要素を最後まで「バブル」します。

以下は、基本的な記述の Java コード例です:

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

ログイン後にコピー

バブルソートの最適化された記述

バブルソートは単純ですが、難しいです。大規模なデータを処理するため、スケーリングする場合、効率が非常に低くなります。ソートの効率を向上させるために、いくつかの最適化措置を追加できます。

一般的な最適化方法は、フラグビットを設定することです。特定のループ内で交換が発生しない場合、つまり配列が既に整っている場合は、ループを早期に終了します。

次は、最適化された書き込みの Java コード例です:

public void optimizedBubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }
}

ログイン後にコピー

バブルソートの最適化された書き込み (比較の数をさらに削減)

In最適化された書き込みにより、比較の数をさらに減らすことができます。バブリング操作の各ラウンドでは、順序なし領域の最大の要素が順序なし領域の最後まで「バブリング」されるため、次のラウンドの順序なし領域の長さは 1 減ります。

この観察に基づいて、内部ループ内の最後のスワップ位置 lastSwapIndex を記録できます。この位置以降の要素はすでに順序どおりに配置されているため、比較する必要はありません。

次は、さらに最適化された Java コード例です:

public void furtherOptimizedBubbleSort(int[] array) {
    int n = array.length;
    int lastSwapIndex;

    for (int i = 0; i < n-1; i++) {
        lastSwapIndex = 0;

        for (int j = 0; j < n-1-i; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                lastSwapIndex = j+1;
            }
        }

        if (lastSwapIndex == 0)
            break;

        n = lastSwapIndex;
    }
}

ログイン後にコピー

概要:

この記事では、Java バブルソートをすばやくマスターするための一般的な記述方法を紹介し、具体的なコード例を示します。これらの記述方法を理解して実践することで、誰もがこの古典的な並べ替えアルゴリズムをより適切に制御して使用できるようになります。もちろん、バブルソートの効率は比較的低いため、大規模なデータをソートする場合は、クイックソートやマージソートなど、より効率的なソートアルゴリズムを選択することをお勧めします。

以上がJavaバブルソートの一般的な書き方と分析を学ぶの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。