Java ソート InsertionSort 挿入ソートの例

インサートソートはダブルバックルのような賭けのようなものです。カードを引くときは、一度に 1 枚ずつカードを取り出し、このカードを前のカードと 1 枚ずつ比較します。このカードを挿入する場所を選択し、順序を整えてからカードをプレイすることがよりスムーズになります。そうしないと、いちいち探すのが面倒になってしまいます。また、トランプの全体的な状況にとっても好ましくありません。下の写真を見てください

初めてクラブを 7 つ引いたとします。並べ替える必要はありません。カードが1枚しかないから

---

それでクラブ

を10枚引きました。 10 は 7 より大きいため、並べ替える必要はありません。

そしてカードを引き続けます。クラブを5本引いていることが分かりました。この時点では躊躇しないでください。2 時は実際には大したことではありません。決定的な折り目

次に、5と10を比較します。 5 は 10 未満なので、位置を交換します。

5 を取り出し、7 と比較してください。 5 は 7 より小さいです。 したがって、5 と 7 の位置を交換して を取得します。

現時点では既に整理されております。 これが原則です。

それは比較的簡単だからです。コードを直接貼り付けてください

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort

パフォーマンス分析 最悪のシナリオは、毎回引かれるカードが最小になることです。このとき、毎回尻尾から頭までトラバースする必要があります。時間はN^2に比例します

ソートされているのが一番良い状態です。すでに整理されているからです。そのため、毎回引いたカードを並べ替える必要がありません。 時間はNに比例します

以上がJava ソート InsertionSort 挿入ソートの例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。