Java クラシック アルゴリズム バブル ソート コード共有

原題: Java の古典的なアルゴリズム: バブルソート (バブルソート)

バブルソートとは何ですか?

バブル ソートは、順序に基づいて要素をペアごとに比較する単純な並べ替えアルゴリズムです。順序が大から小の場合、2 つの要素が相互に比較されると、大きい方が最初にランク付けされ、そうでない場合は、大きい方が後にランク付けされます。バブル選別は大から小への選別と小から大への選別に分かれます。

原則: 2 つの隣接する要素を比較し、値が大きい方の要素を右端に入れ替えます。

アイデア: 2 つの隣接する数値を順番に比較し、小数を前に、大きい数値を後ろに置きます。つまり、最初のパスでは、まず 1 番目と 2 番目の数値を比較し、小数点を前に、大きな数値を後ろに置きます。次に、2 番目の数値と 3 番目の数値を比較し、小数を前に、大きな数値を後ろに置きます。最後の 2 つの数値を比較するまで同様に、小数を前に、大きな数値を後ろに置きます。すべての並べ替えが完了するまで、最初の手順を繰り返します。

例: 配列をソートするには: int[] arr={6,3,8,2,9,1};

最初のソート:

最初のソート: 6 3、6は3より大きい、交換位置: 3 6 8 2 9 1

2番目の並べ替え: 6 と8 比較: 6は、位置を交換せずに8より小さい: 3 6 8 2 9 1

3番目の並べ替え: 8と2 比較してください 8は2より大きい、位置を入れ替える: 3 6 2 8 9 1

、8は9より小さい はより大きい1 、位置の交換: 3 6 2 8 1 9 最初のトリップで合計 5

の比較が行われ、ソート結果:

3 6 2 8 1 9

------------------------------------------------- --------------------

2回目の並べ替え:

1回目の並べ替え: 3と6、3 の比較は6より小さい、位置を交換せず: 3 6 2 8 1 9

2番目の並べ替え: 6と2の比較、 6 はより大きい2、位置交換: 3 2 6 8 1 9

3番目の並べ替え: 6と8の比較、6より大きい8、位置の交換なし: 3 2 6 8 1 9

4番目の並べ替え: 8と1を比較すると、8は1より大きい、位置を交換します: 3 2 6 1 8 9

2 回目の旅行では、合計 4 の比較が実行され、ソート結果は次のとおりです: 3 2 6 1 8 9

--- ---------------------------------------------------- ------- --------

3回目の並べ替え:

1回目の並べ替え: 3と2を比較すると、3はより大きい2、位置を交換: 2 3 6 1 8 9

2番目の並べ替え: 3と6を比較すると、3の方が少ない6より 、位置を交換しないでください: 2 3 6 1 8 9

3番目の並べ替え: 6と1を比較すると、6は1より大きく、位置を入れ替えます: 2 3 1 6 8 9

２つ目合計 3 の比較が行われ、 並べ替え結果: 2 3 1 6 8 9

---------------------- -------------------------------------------------- --

4 回目の並べ替え:

最初の並べ替え: 2 と 3 を比較すると、 2 は 3 より小さく、位置は交換されません: 2 3 1 6 8 9

2 番目の並べ替え: 3 と 1 を比較すると、3 は 1 より大きいため、位置を交換します。 2 1 3 6 8 9 2回目の旅行は合計で

2

の比較、の並べ替え結果: 2 1 3 6 8 9----------------- ------------ -------------------------------------- --

5回目の並べ替え:

最初の並べ替え: 2

と

1を比較すると、2が1より大きく、位置を入れ替えます: 1 2 3 6 8 9 2 回目の旅行 合計

1

の比較が行われ、 並べ替え結果: 1 2 3 6 8 9-------------- ------------ -------------------------------------- -------------

最終結果:

1 2 3 6 8 9

------ ------------------------ ------------------------ --------

次のことがわかります:

N

個の数値を並べ替える必要があり、合計 N-1 の並べ替え、各 i の並べ替えの数時間は(N-i)回なので、二重ループステートメントを使用できます。外側の層はループの回数を制御し、内側の層はそれぞれの回数を制御します。つまり、

for(int i=1;i<arr.length;i++){

    for(int j=1;j<arr.length-i;j++){

    //交换位置

}

バブルソートの利点: ソートが実行されるたびに、より大きな値が見つかるため、比較が 1 つ少なくなります。上の例のように、最初の比較の後、最後の数値が最大の数値である必要があります。2 回目の並べ替えでは、最後の数値を除く他の数値を比較するだけでよく、数値はランク付けされます。 3 番目の比較では、最後の 2 つの数値を除く他の数値のみを比較する必要があります。つまり、比較を行わないと、毎回の旅行ごとに比較が 1 つ減ります。ある程度のアルゴリズムの量。

時間の複雑さの観点から:

1. データが整っていれば、並べ替えを完了するのに 1 回の移動だけで済みます。必要な比較数 とレコード移動数 は両方とも最小値に達します: C_min=n-1; したがって、バブルソートの最適な時間計算量は O _{です。 (n)。}

_{2. 残念ながらデータが逆順の場合は、n-1}の並べ替えを実行する必要があります。各ソート パスには n-i 比較(1≤i≤n-1) が必要で、各比較でレコードを 3 回移動して交換レコードの位置を取得する必要があります。この場合、比較と移動の数は最大値に達します: バブルソートの最悪の時間計算量は: O(n2_)^です。

要約すると、バブルソートの合計平均時間計算量は O(n2₎です。

Java クラシック アルゴリズム バブル ソート コード:

/*
 * 冒泡排序 */public class BubbleSort {
　　public static void main(String[] args) {
　　　　int[] arr={6,3,8,2,9,1};
　　　　System.out.println("排序前数组为：");
　　　　for(int num:arr){
　　　　　　System.out.print(num+" ");
　　　　}
　　　　for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数　　　　　　for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次　　　　　　　　if(arr[j]>arr[j+1]){
　　　　　　　　　　int temp=arr[j];
　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=temp;
　　　　　　　　}
　　　　　　}
　　　　} 
　　　　System.out.println();
　　　　System.out.println("排序后的数组为：");
 　　　　for(int num:arr){
 　　　　　　System.out.print(num+" ");
 　　　　} 
　　}
 }

Java クラシック アルゴリズム バブル ソートの詳細については、php 中国語 Web サイトに注目してください。