Java ソートアルゴリズムの概要 (パート 3): バブルソート

バブルソートは、計算時間が O(n^2) のコンピュータソート方法です。ヒープソートやクイックソートの O(nlogn、基数 2) ほどではありませんが、次の 2 つの利点があります。

1. 「プログラミングの複雑さ」が非常に低く、コードを書くのが簡単です。

2. 安定しています。ここでの安定性とは、元のシーケンス内の同じ要素の相対的な順序がソートされたシーケンスでも維持されることを意味しますが、ヒープソートやクイックソートは安定していません。

ただし、一方向および双方向のマージソートやアンバランスバイナリツリーソートはバブルソートよりも高速で安定性がありますが、ヒープソートやクイックソートほど高速ではありません。バブルソートは、n-1 ラウンドのサブソートによって完了します。i ラウンド目のサブソートは、1 番目の数字から ni 番目の数字までです。i 番目の数字が次の数字よりも大きい場合 (昇順、そうでない場合は降順)、2 つの数字が交換されます。

バブルソートアルゴリズムは安定しており、追加スペースは O(1)、比較と交換の時間計算量は O(n^2) です。これは適応型であり、基本的なソートアルゴリズムの時間計算量は O(n) です。バブルアルゴリズムには挿入アルゴリズムに類似した多くの特性がありますが、システムオーバーヘッドがわずかに高くなります。

選別プロセス

ソートされた配列 R [1..N] が垂直に立っていて、各データ要素が重さのあるバブルであると仮定します。軽いバブルは重いバブルの下には置けないという原則に従って、配列 R は下から上にスキャンされます。この原則に違反する軽いバブルが見つかると、そのバブルは上方に「浮かぶ」ようになります。このプロセスは、任意の 2 つのバブルの最も軽いバブルが上に、重いバブルが下にくるまで繰り返されます。

コード実装:

 // バブルソート
パブリッククラスBubbleSort {
パブリック静的voidソート(比較可能な[]データ) {
 // 配列の長さ
int len =データ.長さ;
 (int i = 0 ; i <  長さ- 1; i++) {
 // 一時変数
比較可能なtemp = null ;
 // スワップフラグ。false はスワップしないことを意味します
ブール値isExchanged = false ;
 (int j = len - 1; j > i; j--) の場合 {
 // data[j]がdata[j - 1]より小さい場合は、
 if (data[j].compareTo(data[j - 1]) <   0 ) {
 temp =データ[j];
データ[j] = データ[j - 1];
データ[j - 1] = temp;
 // 交換が発生したため、交換フラグが true に設定されます
isExchanged = true ;
 }// 終了
}// 終了
// このソートでは交換は発生しないため、効率を上げるためにアルゴリズムを早期に終了する
交換された場合
戻る;
 }// 終了
}// 終了
}// ソート終了
パブリック静的voidメイン(String[] args) {
 // JDK1.5以降では、基本データ型は自動的にボックス化されます
// intやdoubleなどの基本型のラッパークラスはComparableインターフェースを実装しています
比較可能[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
ソート(c);
 (比較可能なデータ: c) {
 System.out.println(データ);
 }
 }
 }