Java バブル ソートの詳細な紹介 (コード例)

この記事では、Java バブル ソートの詳細な紹介 (コード例) を紹介します。一定の参考値があります。困っている友人は参照してください。お役に立てば幸いです。役に立ちました。

1. はじめに

これはソート アルゴリズム シリーズの最初の記事なので、もう少し説明します。

ソートは最も一般的なアルゴリズムの 1 つです。現在、多くのプログラミング言語には、Java の Arrays.sort() メソッドなどのいくつかのソート アルゴリズムが統合されています。このメソッドを使用すると、内部的なアルゴリズムを気にせずに直接呼び出すことができます。実装の詳細. 実際のソフトウェア開発でもよく使われます。しかし、開発者の観点から見ると、何が起こっているのかを知るためには、その理由を知る必要があります。より多くの並べ替えアルゴリズムを練習すると、いくつかの並べ替えメソッドの基礎となる実装の詳細を知ることができるだけでなく、思考力を鍛え、プログラミング能力を向上させることもできます。現在、多くの技術面接には基本的な並べ替えアルゴリズムも含まれているため、さらに練習することは有益です。 (推奨: Java ビデオ チュートリアル )

この記事に含まれるコードはすべて Java で実装されていますが、Java 言語の機能はあまり含まれていないため、詳細なコメントを追加します。コードを理解し、使い慣れたプログラミング言語に変換するのに役立ちます。

一般的なソート アルゴリズムは 10 個あります:

• バブル ソート、選択ソート、挿入ソート、平均時間計算量は O(n² )
• ヒル ソート、マージ ソート、クイック ソート、およびヒープ ソートの平均時間計算量は O(nlogn)です。
• カウンティング ソート、基数ソート、およびバケット ソートの平均時間計算量は O(nlogn) です。それは O(n k)

特定の並べ替えアルゴリズムの説明を始める前に、まず 2 つの概念を理解する必要があります:

1. 所定の並べ替え: 並べ替えのプロセスを指します。追加のストレージ スペースを占有せず、スペースの複雑さは O(1) です。
2. ソートアルゴリズムの安定性: 安定したソートとは、ソート後に同じ要素の順序が変更されないことを意味し、それ以外の場合は不安定と呼ばれます。例: 配列 [3, 5, 1, 4, 9, 6, 6, 12] には 6 が 2 つあります (区別するために、6 の 1 つを太字にしています)。ソート後は次のようになります。 : [1, 3, 4, 5, 6, 6, 9, 12] (太字の 6 がまだ前にあります)。これは、これが安定した並べ替えアルゴリズムであることを示しています。

2. もっと身近な話

バブル ソートの考え方は実際には非常に単純で、1 つのデータのサイズを隣接するデータと比較します。大小関係が満たされている場合は、これら 2 つのデータの位置を交換します。この操作を繰り返すことでデータを並べ替えることができます。

たとえば、配列 a[3,5,1,4,9,6] がある場合、最初のバブリング操作は次のようになります。

この操作を繰り返し、6 バブル後にデータのソートが完了します。

このアイデアによれば、バブル ソートを実装する次のコードを簡単に作成できるはずです:

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

ただし、このソート アルゴリズムは、バブリングでデータ交換がない場合にも最適化できます。操作 この場合、ソートが完了したことを意味し、バブリング操作を実行する必要はありません。たとえば、上の例では、最初のバブルの後、データは [3,1,4,5,6,9] になり、別のバブルの後、データは [1,3,4,5,6,9] になります。 ] の場合、この時点でソートは完了しており、ループを終了できます。

したがって、この配列を並べ替えるには、上記のコードを完了するために 6 つのバブルが必要ですが、そのうち 4 つは不要です。したがって、コードを最適化できます:

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

わかりました、バブル ソートの基本的な考え方とコードが実装されました。最後に要約しましょう:

1. バブル ソートはデータ比較に基づいています。
2. 最良の場合の時間計算量は O(n)、最悪の場合の時間計算量は O(n²)、平均の時間計算量は O(n²)
3. バブルソートはインプレースソートアルゴリズムであり、安定しています。

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