Java でのバブルソートの簡単な分析例

この記事では主に Java の単純なバブルソートの例を詳しく紹介します。興味のある方は参考にしてください

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

隣接する要素の各ペアに対して、最初のペアから始めて最後のペアで終わるまで、同じことを行います。この時点では、最後の要素が最大の数値である必要があります。

最後の要素を除くすべての要素に対して上記の手順を繰り返します。

比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

2. 実装アイデア

外側のループ変数を i に設定し、内側のループ変数を j に設定して、二重ループを使用して実装します。ソートする必要がある数値が n 個ある場合、外側のループは n-1 回繰り返され、内側のループは n-1、n-2、...、1 回繰り返されます。毎回比較される 2 つの要素は、内側のループ j に関連しています。それらはそれぞれ、a[j] と a[j+1] で識別できます。i の値は 1、2、...、n-1 です。 . 、各 i について、j の値は 0、1、2、...n-i です。

配列の長さが N であると仮定します:

1。前後の隣接する 2 つのデータを比較し、前者のデータが後者のデータより大きい場合、2 つのデータを交換します。
2.このようにして、配列の 0 番目のデータから N-1 番目のデータまで移動した後、最大のデータは配列の N-1 番目の位置に「沈みます」。

3. N=N-1。N が 0 でない場合は、前の 2 つの手順を繰り返します。そうでない場合は、並べ替えが完了します。

3. コードの実装

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      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]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

4. パフォーマンス分析

レコードシーケンスの初期状態が「正の順序」の場合、バブルソートプロセスはソート中に一度だけソートする必要があります。 process レコードを移動せずに n-1 回の比較のみが必要ですが、逆に、レコード シーケンスの初期状態が「逆順」の場合は、n(n-1)/2 回の比較とレコードの移動が必要です。したがって、バブル ソートの合計時間計算量は O(n*n) になります。

5. アルゴリズムの最適化

バブルソート法の欠点と改善方法:

まず、ソートプロセス中、最終ソートが実行された後、データは完全にソートされていますが、プログラムはソートが完了したかどうかを判断できません。この問題を解決するには、フラグ flag を設定し、その初期値を true に設定して、並べ替えが開始される前にフラグの値を true に設定し、データ処理を実行します。交換する場合は、フラグを false に変更します。新しいソートの開始時に、このフラグをチェックします。このフラグが false の場合は、前回データが交換されなかったことを意味し、それ以外の場合は、バブルでソートが実行されます。従来のバブル ソート アルゴリズムや近年改良されたアルゴリズムでは、1 回のスキャンでデータ交換が行われたかどうかの情報のみが記録されます。データ交換が行われる場所は記録されません。情報は処理されません。この情報を最大限に活用するために、グローバル スキャンの逆順データ ペアごとにローカル バブル ソートを実行できます。これはローカル バブル ソートと呼ばれます。ローカル バブル ソートの時間計算量はバブル ソート アルゴリズムと同じであり、必要なキーワードの比較と移動の数は順方向でも逆順でもまったく同じです。ローカル バブル ソートとバブル ソート間で移動するデータの数は常に同じであり、ローカル バブル ソートで必要なキーワードの比較の数は多くの場合バブル ソートよりも少ないため、これは、ローカル バブル ソートには、比較の平均数が減少するため、比較回数が少ないという利点がプログラムの複雑さによって生じる追加のオーバーヘッドを相殺するのに十分ではない場合、およびデータ量が大きい場合に、ローカルの時間パフォーマンスが低下します。バブル ソートはバブル ソートよりも大幅に優れています。 N 個の順序なしデータについて、バブル ソートを実行すると、k 番目のデータと k+1 番目のデータが逆順の場合、k+1 番目のデータに対して順方向バブル ソートが実行されるため、Moveそれを適切な位置に調整します。つまり、前の k+1 データを正のシーケンスに調整します。このバブリング手法は最初の k+1 データのみをバブリングするため、これをローカル バブリング

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      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]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

と呼びます。

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