バブルソートの詳細(xì)説明: 簡(jiǎn)単な並べ替えアルゴリズム

バブル ソートは、最も単純な並べ替えアルゴリズムの 1 つです。これは、隣接する要素を繰り返し比較し、順序が間違っている場(chǎng)合は交換することで機(jī)能します。たとえば、並べ替え順序が昇順の場(chǎng)合、隣接する要素が比較され、大きい要素が右側(cè)に配置されます。各反復(fù)では、ソートされていない要素のみを比較し、最大の要素を配列內(nèi)のソートされていない要素の最後の位置に配置します。

このアルゴリズムは、水面に上昇する泡のように、反復(fù)ごとに要素が配列の右側(cè)に向かって移動(dòng)するため、バブル ソートという名前が適切に付けられています。

バブルソートの仕組み

この配列を昇順に並べ替えたいとします:

最初の反復(fù)

最初の反復(fù)では、最大の要素を配列の末尾に移動(dòng)しようとします。したがって、隣接する要素を繰り返し比較し、順序が間違っている場(chǎng)合は交換します。

正しい位置に移動(dòng)された要素は並べ替えられたとみなされます。

次の反復(fù)

配列がソートされるまで、このプロセスがすべての反復(fù)で繰り返されます。ソートされた要素はすでに正しい順序になっているため、各反復(fù)ではソートされていない要素のみを比較します。

配列を n-1 回繰り返します。ここで、n は配列の長(zhǎng)さです。つまり、配列には 6 つの要素があるため、配列を 5 回繰り返すだけです。これは、5 回目の反復(fù)の後、5 つの要素が正しい位置に配置され、ソートされていない最後の要素がソートされているとみなされるためです。すべての反復(fù)が完了すると、ソートされた配列が得られます。

バブルソートの実裝

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循環(huán)遍歷數(shù)組 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比較相鄰元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

このコードを?qū)g行すると、コンソールに次の出力が表示されます:

<code>未排序數(shù)組: [8, 2, 6, 4, 9, 1]
已排序數(shù)組: [1, 2, 4, 6, 8, 9]</code>

バブル ソートのこの実裝では、配列がすでにソートされている場(chǎng)合でも、毎回配列を反復(fù)処理します。コードをさらに最適化して、配列がソートされた後にソートを停止することができます。

バブルソートの最適化

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循環(huán)遍歷數(shù)組 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比較相鄰元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果沒有交換，則數(shù)組已排序
        if(!swapped) break;
    }
}

この実裝では、既にソートされている配列をソートしようとすると、反復(fù)処理は 1 回だけ行われ、ソートが行われなくなると停止します。

バブルソートの複雑さ

時(shí)間計(jì)算量:

最良のケース (O(n)):

最良のシナリオは、入力配列がすでにソートされていることです。このアルゴリズムは配列を 1 回反復(fù)して並べ替えられているかどうかを確認(rèn)するだけで、交換は実行しません。

平均ケース (O(n2)):

入力配列要素がランダムな順序である場(chǎng)合。アルゴリズムは複數(shù)回反復(fù)し、スワップを?qū)g行して配列を並べ替える必要があります。

最悪の場(chǎng)合 (O(n2)):

最悪のシナリオは、入力配列が逆順にソートされることです。このアルゴリズムは n-1 回の反復(fù)を経て、最大數(shù)のスワップを?qū)g行します。

空間複雑度 O(1):

バブル ソートはインプレース ソート アルゴリズムです。つまり、入力配列のサイズに比例する追加のメモリは必要ありません。

結(jié)論

バブル ソートは、理解と実裝が簡(jiǎn)単なアルゴリズムです。ただし、時(shí)間の複雑さが高いため、大規(guī)模なデータセットの処理には適していません。バブル ソートは、小さなデータ セットを扱う場(chǎng)合、または複雑さを気にしない場(chǎng)合に使用できます。

以上がバブル ソート アルゴリズムを理解する (Java の例付き)の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。