Python で Hill ソート アルゴリズムを記述するにはどうすればよいですか?

ヒル ソート アルゴリズムを Python で作成するにはどうすればよいですか?

ヒル ソート (シェル ソート) は、挿入ソートのアルゴリズムを改良したもので、一定間隔で要素を比較して要素を移動し、移動回数を削減します。ヒル ソートの中心的な考え方は、ソートする要素を特定の間隔に従ってグループ化し、各グループに対して挿入ソートを実行し、間隔が 1 になるまで継続的に間隔を減らし、最後に完全な挿入ソートを実行することです。

以下では、Python を使用して Hill ソート アルゴリズムを記述する方法を詳しく紹介します。

まず、挿入ソートを実装する関数を作成する必要があります。挿入ソートの中心的な考え方は、既にソートされている前のシーケンスに現在の要素を挿入することです。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

次に、並べ替えるリストをパラメータとして受け取る Hill 並べ替え関数を作成します。

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔设置为列表长度的一半
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2  # 缩小间隔

最後に、ヒル ソートの正確さを検証するテスト関数を作成します。

def test_shell_sort():
    arr = [12, 34, 55, 23, 8, 17, 45, 91]
    shell_sort(arr)
    assert arr == [8, 12, 17, 23, 34, 45, 55, 91]
    print("希尔排序测试通过！")

if __name__ == "__main__":
    test_shell_sort()

テスト関数の実行後、エラーが報告されず、「ヒル ソート テストに合格しました!」というプロンプトが出力されれば、ヒル ソートの実装が正しいことを意味します。

ヒル ソートの時間計算量は、選択した間隔シーケンスに関連しています。最適な間隔シーケンスはまだ見つかりません。ヒル ソートの平均時間計算量は約 O(n^1.3) で、最悪の場合の時間計算量は約 O(n^2) です。

ヒル ソートは効率的なソート アルゴリズムです。挿入ソートと比較して、最初に挿入ソートの要素を部分的に順序付けることができるため、その後の比較および移動操作が削減され、効率が向上します。リストをすばやく並べ替えたい場合は、Hill 並べ替えアルゴリズムを使用してみてください。

以上がPython で Hill ソート アルゴリズムを記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。