ヒルソートJavaコード実装

ヒルソート
ヒルソートは、ヒル(Donald Shell)が1959年に提案したソートアルゴリズムである.ヒルソートは、単純な挿入ソートが改良されたより効率的なバージョンであり、インクリメンタルソートの縮小とも呼ばれ、O(n 2)を突き破る最初のアルゴリズムの1つである挿入ソートでもある.挿入ソートとは異なり、距離の遠い要素を優先的に比較します.ヒルソートは、インクリメンタルソートの縮小とも呼ばれます.
ヒルソートは要素を表の一定の増分グループに分け、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が徐々に減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、配列全体がグループに分けられ、アルゴリズムは終了する.
アルゴリズムの説明
ヒルソートの基本手順を見てみましょう.ここでは、増分gap=length/2を選択し、増分を縮小してgap=gap/2の方法で継続します.この増分選択は、増分シーケンスと呼ばれる{n/2,(n/2)/2...1}を1つのシーケンスで表すことができます.ヒルソートのインクリメンタルシーケンスの選択と証明は数学的な難題であり,我々が選択したこのインクリメンタルシーケンスは比較的よく用いられ,ヒルが提案したインクリメンタルでもあり,ヒルインクリメンタルと呼ばれているが,実はこのインクリメンタルシーケンスは最適ではない.ここでは、ヒル増分を例に挙げます.
まず、並べ替え対象の記録シーケンス全体をいくつかのサブシーケンスに分割して、それぞれ直接挿入並べ替えを行い、具体的なアルゴリズムの説明:

増分シーケンスt 1,t 2,...,tkが選択され、ti>tj,tk=1である.

増分シーケンス個数kに従って、シーケンスをk回並べ替える.

の各ソートは、対応するインクリメンタルtiに基づいて、並べ替えられるシーケンスをいくつかの長さmのサブシーケンスに分割し、各サブテーブルをそれぞれ直接挿入ソートする.増分係数が1の場合、シーケンス全体が1つのテーブルとして処理され、テーブル長はシーケンス全体の長さとなります.

アルゴリズム解析

時間複雑度:O(nlogn)

空間複雑度:O(1)

安定性:不安定

コード実装

public class ShellSort {
    public static void shellSort(int[] arr) {
        //                ，      。
        if (arr == null || arr.length <= 1) return;
        //       。
        int gap = arr.length / 2;
        // gap   0        。
        while (gap != 0) {
            //           。
            for (int i = gap; i < arr.length; i++) {    // i           。
                int value = arr[i];
                int j = i - gap;    // j   i      ，      gap。

                // j < 0      ，   j           。
                //    arr[j] <= value      ，   j   value        。
                for (; j >= 0 && arr[j] > value; j -= gap) {
                    arr[j + gap] = arr[j];  //       。
                }
                arr[j + gap] = value;

            }
            //               。
            print(arr);

            //     。
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};

        System.out.print("   :  ");
        print(arr);

        shellSort(arr);

        System.out.print("   :  ");
        print(arr);
    }

    //     
    public static void print(int[] arr) {
        if (arr == null)    return;

        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
/*
   :  6 9 1 4 5 8 7 0 2 3 
6 7 0 2 3 8 9 1 4 5 
0 1 3 2 4 5 6 7 9 8 
0 1 2 3 4 5 6 7 8 9 
   :  0 1 2 3 4 5 6 7 8 9 
*/