バブル ソート アルゴリズムを理解する (Java の例付き)

バブルソートの詳細説明: 簡単な並べ替えアルゴリズム

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

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

バブルソートの仕組み

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

最初の反復

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

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

次の反復

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

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

バブルソートの実装

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

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

        // 循环遍历数组 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;
                }
            }
        }
    }
}

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

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

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

バブルソートの最適化

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

    // 循环遍历数组 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;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

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

バブルソートの複雑さ

時間計算量:

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

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

平均ケース (O(n²)):

入力配列要素がランダムな順序である場合。アルゴリズムは複数回反復し、スワップを実行して配列を並べ替える必要があります。

最悪の場合 (O(n²)):

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

空間複雑度 O(1):

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

結論

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

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