バブルソートアルゴリズムの Java 実装とその簡単な最適化例

原則

バブル ソートはおそらくすべてのプログラマーが使用するアルゴリズムであり、最もよく知られているアルゴリズムの 1 つでもあります。
考え方は複雑ではありません:
n 個の要素を持つ配列 arr[] をソートするとします。
1. n=1 の場合: 当然、調整する必要はありません。 (実際、この議論は不要だと思われます)
2. n>1 の場合:
(1) 最初の要素から開始し、前の要素が後の要素より大きい場合は、最後の要素で比較します。結果として、前者は間違いなく後続するでしょう。したがって、これら 2 つの要素を交換します。次に、次の 2 つの隣接する要素を比較します。これは、要素の最後のペアが比較され、最初の並べ替えラウンドが完了するまで続きます。最後の要素が配列内で最大であることが確実です (比較的大きな要素が毎回最後に配置されるため)。
(2) 上記のプロセスを繰り返します。今回は最後の 1 つはすでに並んでいるので考慮する必要はありません。
(3) これは、残りの要素が 1 つだけになるまで行われ、この要素が最小になるとソートが完了します。明らかに、n-1 ソートが行われます。
上記のプロセスでは、並べ替えるたびに（または「ラウンド」と呼ばれます）、数値が特定の位置から最終位置までゆっくりと「浮遊」します（概略図を描き、配列を垂直に描いて確認します）、それはバブルのようなものですソートするので「バブルソート」と呼ばれます。

コード実装:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

アルゴリズムのパフォーマンス/複雑さ
ループ変数の増分と初期化の時間は無視します。まずアルゴリズムの比較回数を分析します。改善を加えていない上記のバブル ソートでは、入力データに関係なく n-1 ラウンドのソートが実行され、各ラウンドのソートに必要な比較の数が n-1 から 0 に減少することが簡単にわかります。したがって、比較の合計数は、(n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2 となります。 （二乗の計算方法が分からないので、ここでは二乗をn^2で表します。以下同様）
代入の数を見てみましょう。ここでの割り当ては交換操作を指します。上記のコードでは、1 回の交換は 3 回の割り当てに相当します。毎回スワップする必要はないため、代入演算の回数は入力データに関係します。最良の場合、つまり最初から順序付けされた場合、割り当ての数は 0 です。 最悪の場合、割り当て数は (n-1)n/2 になります。入力データが均一 (または「完全にランダム」) に分散されていると仮定すると、比較の数の約半分のスワップが発生します。上記の結果から、平均的なケースでは、割り当ての数は 3/2 * (n^2)/2 = 3/4*(n^2) であることがわかります。
要約すると、状況に関係なく、 、バブル ソートの空間複雑さ (余分な空間) は常に O(1) です。

改善
最適な時間計算量を示します。これは、データが完全に順序付けされている場合は O(n) です。それ以外の場合は、ほとんどの場合 O(n^2) です。したがって、アルゴリズムは、データが基本的に順序付けされている場合に最高のパフォーマンスを発揮します。
しかし、上記のコードの複雑さはどのようにして O(n) になるのでしょうか?実際、上記は基本的な考え方に焦点を当てているため、最良の場合のアルゴリズムの複雑さを O(n) にするには、いくつかの改良が必要です。実際、大量のデータを使用する場合にはバブル ソートはほとんど使用されないため、少量のデータを使用する場合にブール変数を追加すると追加のオーバーヘッドが発生します。したがって、上記の改良されたアルゴリズムは純粋に理論的なものであると個人的には考えています。通常、バブルソートの場合は前者を記述するだけです。

アルゴリズムの安定性

隣接する要素が等しい場合、それらの位置を交換する必要がないため、バブルソートは安定したソートであることが簡単にわかります。

アルゴリズムに適用できるシナリオ

バブル ソートはシンプルなアイデアとシンプルなコードを備えており、小さなデータの並べ替えに特に適しています。ただし、アルゴリズムが複雑なため、データ量が多い場合の使用には適していません。データが大量にある場合に使用する必要がある場合は、選択ソートなどのアルゴリズムを改善するのが最善です。

バブル ソート アルゴリズムの Java 実装とその簡単な最適化例に関するその他の関連記事については、PHP 中国語 Web サイトに注目してください。