バブルソート

バブル ソートは、複数のフェーズで配列をソートします。要素の順序が正しくない場合、各パスは隣接する要素を連続して交換します。バブル ソート アルゴリズムは、配列を複数回通過します。各パスで、連続する隣接するペアが比較されます。ペアが降順の場合、その値は交換されます。それ以外の場合、値は変更されないままになります。この手法は、バブル ソート または シンキング ソート と呼ばれます。これは、小さい値が徐々に上部に向かって「バブル」し、大きい値が下部に沈むためです。最初のパスの後、最後の要素が配列内で最大になります。 2 回目のパスの後、最後から 2 番目の要素が配列内で 2 番目に大きい要素になります。このプロセスは、すべての要素がソートされるまで継続されます。

下の図 (a) は、6 つの要素 (2 9 5 4 8 1) の配列に対するバブル ソートの最初のパスを示しています。最初のペア (2 と 9) の要素を比較します。これらはすでに順序が整っているため、交換する必要はありません。 2 番目のペア (9 と 5) の要素を比較し、9 は 5 より大きいため、9 と 5 を交換します。 3 番目のペア (9 と 4) の要素を比較し、9 と 4 を交換します。 4 番目のペアの要素を比較します。ペア (9 と 8) を比較し、9 と 8 を交換します。 5 番目のペア (9 と 1) の要素を比較し、9 と 1 を交換します。以下の図では、比較されているペアが強調表示され、すでに並べ替えられた番号が斜体で表示されています。 🎜>

最初のパスでは、最大の数値 (9) が配列の最後に配置されます。 2 番目のパスでは、以下の図 (b) に示すように、要素のペアを比較して順序付けします。配列内の最後の要素がすでに最大であるため、最後のペアを考慮する必要はありません。 3 番目のパスでは、下の図 (c) に示すように、最後の 2 つの要素を除いて要素のペアを比較し、順番に並べ替えます。これらの要素はすでに順番に並んでいるからです。したがって、k 番目のパスでは、最後の k - 1 個の要素はすでに順序付けされているため、考慮する必要はありません。

バブルソートのアルゴリズムは以下のコードで説明されています。

for (int k = 1; k // k 番目のパスを実行します
for (int i = 0; i if (リスト[i] > リスト[i + 1])
list[i] を list[i + 1] と交換します;
}
}
パス内で交換が行われない場合は、すべての要素がすでにソートされているため、次のパスを実行する必要がないことに注意してください。このプロパティを使用すると、以下のコードと同様に、上のコードのアルゴリズムを改善できます。

ブール値 needNextPass = true;

for (int k = 1; k // 配列はソートされる可能性があるため、次のパスは必要ありません
needNextPass = false;
// k 番目のパスを実行します
for (int i = 0; i < list.length – k; i++) {
if (リスト[i] > リスト[i + 1]) {
list[i] を list[i + 1] と交換します;
needNextPass = true; // 次のパスがまだ必要です
}
}
}

アルゴリズムは以下のコードで実装できます

最良の場合、バブル ソート アルゴリズムは、配列が既にソートされていることを確認するために最初のパスのみを必要とし、次のパスは必要ありません。最初のパスでは比較の数が n - 1 であるため、バブル ソートの最良の場合の時間は O(n) です。

最悪の場合、バブル ソート アルゴリズムには n - 1 回のパスが必要です。最初のパスでは、n - 1 個の比較が行われます。 2 番目のパスでは n - 2 回の比較が行われます。等々;最後のパスでは 1 つの比較が行われます。したがって、比較の合計数は次のようになります:

したがって、バブルソートの最悪の場合の時間は O(n^2) です。

以上がバブルソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。