ヒルソート(python)

4.ヒルソート(インクリメンタルソート縮小)
4.1アルゴリズム思想
ヒルソートは、ソートを挿入する最適化であり、「インクリメンタルソートの縮小」とも呼ばれ、ソートアルゴリズムを直接挿入するより効率的な改良バージョンです.ヒルソートは、レコードを下付きの一定の増分でグループ化し、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、ファイル全体がグループに分けられ、アルゴリズムは終了する.
まず、正の整数d 1をとる方法は、実質的にパケット挿入方法である.
4.2アルゴリズム分析
ヒルソートの時間的複雑さは、増分シーケンスの選択に関係し、例えば、ヒル増分時間の複雑さはO(n²),一方,Hibbard増分のヒルソートの時間的複雑度はO(n^(3/2))であり,ヒルソートの時間的複雑度の下限はn*log 2 nであった.ヒルソートは高速ソートアルゴリズムが速いO(n(logn))を持たないため,中程度の大きさの規模は良好であり,非常に大規模なデータソートには最適ではない.
Shellソートの実行時間はインクリメンタルシーケンスに依存する.良いインクリメンタルシーケンスの共通の特徴:1最後のインクリメンタルは1でなければならない.②シーケンス内の値(特に隣接する値)が互いに倍数になることは極力避けるべきである.
このアルゴリズムは余分な空間を必要とせず,時間複雑度はo(1)である.
4.3アルゴリズムプロセス
まず、ソート対象の要素シーケンス全体を増分分割していくつかのサブシーケンスに直接挿入ソートし、具体的なアルゴリズムの説明:

増分シーケンスt 1,t 2,...,tkを選択し、t 1>t 2>...>tk,tk=1;

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

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

4.4 pythonコード

def  shellSort(numList):
    n = len(numList)
    if n == 0 or n == 1:
        return numList
    gap = n // 2
    while gap >= 1:
        for i in range(gap,n):
            #   gap    ，             (               ，          )
            tempindex = i
            while tempindex >= gap and numList[tempindex - gap] > numList[tempindex]:
                numList[i - gap], numList[tempindex] = numList[tempindex],numList[tempindex - gap]
                tempindex -= gap
                #               ，                 gap
        gap = gap // 2
    return numList
numlist = [4,5,7,8,6,1,2,3,4]
print(shellSort(numlist))
#      ：[1, 2, 3, 4, 4, 5, 6, 7, 8]