Javaで単純なソートを実装する方法

並べ替えはデータ処理において非常に一般的かつ中心的な操作です。実際のプロジェクト開発では手動で実装する必要がある可能性はわずかですが、結局のところ、は各言語のクラス ライブラリ内のクラスであり、並べ替えアルゴリズムの実装は多数あります。しかし、こうした微妙な考え方を理解することは、私たちにとって依然として大きな有益です。この記事では、選択、バブリング、挿入という 3 つの最も基本的なアルゴリズムについて簡単に説明します。

まず、配列要素を交換する関数を定義します。この関数は、並べ替え時に呼び出すことができます。

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

単純な選択による並べ替え

単純な選択による並べ替えは、最も単純で直感的なアルゴリズムです。すべての要素がソートされるまで、各パスでソート対象のデータ要素から最小 (または最大) の要素が最初の要素として選択されます。単純な選択ソートは不安定なソートです。

アルゴリズムが実装されると、最小要素が決定されるたびに、継続的な比較と交換を通じて最初の位置が現在の最小値になります。交換は比較的時間のかかる操作です。実際、現在の最小要素が完全に決定されるまでは、これらのやり取りが無意味であることが簡単にわかります。比較ごとに小さい方の要素の配列添字のみを格納する変数 min を設定できます。ループが終了すると、この変数は現在の最小要素の添字を格納し、交換操作を実行します。コードの実装は非常に簡単なので、見てみましょう。

コードの実装

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

単純な選択ソートが上記で最適化された後、配列の元の配置に関係なく、比較の数は変化しません。交換演算の場合、最良の場合、配列は次のようになります。完全に配列が逆順の場合は交換動作は不要であり、最悪の場合、つまり配列が逆順の場合、交換回数はn-1回となります。まとめると、時間計算量は O(n2) です。

バブル ソート

バブル ソートの基本的な考え方は、隣接する要素をペアごとに比較し、順序が逆の場合はそれらを交換することです。このようにして、各パスは最小または最大の要素を先頭に「フローティング」し、最終的に完全な順序を達成します

コード実装

バブル ソート中プロセスでは、特定のトリップが交換操作なしで完了した場合、たとえば、配列 [5,4,1,2,3] はバブリングを 2 回実行します。つまり、2 つの外側のループの後、5 と 4 が最終的な値に調整されます。位置 [1,2,3,4,5]。この時点では、3 番目のループを実行した後、一度も交換が行われていないため、残りのシーケンスはすでに順番に並んでおり、ソート操作を完了できます。 #上記のバブル実装によると、元の配列自体が順序付けされている場合 (これが最良の場合)、n-1 回の比較だけで完了できます; 逆の順序の場合、比較の回数は n-1 n- です2 ... 1= n(n-1)/2、交換回数と比較回数は同じです。したがって、その時間計算量は依然として O(n2) です。全体として、バブル ソートのパフォーマンスは、上記の選択ソートよりもわずかに劣ります。

直接挿入ソート

直接挿入ソートの基本的な考え方は、すべての要素が挿入されるまで、各ステップで以前にソートされたシーケンスにソート対象のレコードを挿入することです。

コードの実装

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

最良の場合、単純な挿入ソートは要素を交換せずに n-1 回比較する必要があり、時間計算量は O です。 ( n); 最悪の場合でも、時間計算量は依然として O(n2) です。ただし、配列要素がランダムに配置されている場合は、挿入ソートの方が上記 2 つのソートよりも優れています。

以上がJavaで単純なソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。