ホームページ >バックエンド開発 >Python チュートリアル >Python でヒルソートアルゴリズムを実装する方法

Python でヒルソートアルゴリズムを実装する方法

WBOY
WBOY転載
2023-05-10 10:25:21786ブラウズ

    アルゴリズムの説明

    ヒル ソートは、「縮小増分ソート」とも呼ばれ、挿入ソートを最適化することによって生成されるソート アルゴリズムです。その実行のアイデアは、配列内の要素を添え字の増分にグループ化し、要素の各グループを挿入して並べ替え、増分を減らし、増分が 1 に達するまで前の手順を繰り返すというものです。

    一般的に言えば、Hill ソートの時間計算量は O(n1.3) ~ O(n2) であり、これは増分サイズに依存します。 Hill ソートの空間計算量は O(1) であり、不安定なソート アルゴリズムです。ヒル ソートを実行する場合、要素の 1 つの移動が複数の要素にまたがる場合があり、これにより複数の移動が相殺され、効率が向上することがあります。

    次は、(配列の長さ/2) を初期増分として使用する昇順ヒル ソートです。ソートの各ラウンドの後、増分は半分に減ります。

    ステップ 1:

    図 2-28 に示すように、最初の要素から開始して、増分 4 でグループ化します。増分が 4 の場合、グループ内の要素は 2 つだけであることがわかります。そうでない場合、要素の添字は配列の範囲を超えます。

    Python でヒルソートアルゴリズムを実装する方法

    ステップ 2:

    図 2-29 に示すように、グループ内の要素を挿入して並べ替えます。

    Python でヒルソートアルゴリズムを実装する方法

    3 番目のステップ:

    図 2-30 に示すように、引き続き同じ方法を使用して、グループ内の要素をグループ化、挿入、並べ替えます。彼らが秩序あるように。

    Python でヒルソートアルゴリズムを実装する方法

    配列全体のすべての数値を調べ終わると、このラウンドの並べ替えは終了します。増分を半分に減らし、次の並べ替えラウンドに進みます。

    ステップ 4:

    図 2-31 に示すように、増分が 2 の場合、各グループの要素が増加し、グループの総数が減少していることがわかります。各グループを横断するまで、各グループ内の要素の挿入ソートを続けます。

    Python でヒルソートアルゴリズムを実装する方法

    5 番目のステップ:

    ソートの最終ラウンドは図 2-32 に示されており、この時点で増分は再び半分に減ります。増分は 1 で、これは配列全体に対して挿入ソートを実行することと同じであり、これがソートの最終ラウンドです。

    Python でヒルソートアルゴリズムを実装する方法

    最後の選別ラウンドが終了すると、ヒル全体の選別が終了します。

    コードの実装

    for ループでは、各グループの最初の要素を挿入して並べ替える必要がなく、添字が 0 から step-1 の間にあるため、最初の要素から開始します。添字ステップのトラバース。

    フローチャートのアプローチをシミュレートしたい場合は、2 つのループを使用する必要があることに注意してください。最初のグループで、次に同じグループ内の要素を一度に順序付けします。効率を向上させるために、for ループを直接使用し、数値を走査するたびに、その数値が含まれるグループが挿入され、ソートされます。この走査は、挿入ソートの順序要件も満たします。挿入ソートでは、現在の添え字の値を変更する必要があるため、変数 ind を使用して現在の添え字を保存し、for ループに影響を与えないようにします。

    通常の挿入ソートは、増分 1 のヒル ソートと同等です。要素間のヒル ソートは、実際には増分が変わるだけであり、論理的には通常の挿入ソートと変わりません。

    ヒルソートコード:

    nums = [5,3,6,4,1,2,8,7]
    def ShellSort(nums):
      step = len(nums)//2         #初始化增量为数组长度的一半
      while step > 0:           #增量必须是大于0的整数
       for i in range(step,len(nums)): #遍历需要进行插入排序的数
         ind = i
         while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
          nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
          ind -= step
       step //= 2           #增量缩小一半
      print(nums)
    ShellSort(nums)

    プログラムを実行すると、出力結果は次のようになります:

    [1,2,3,4,5,6,7,8]

    以上がPython でヒルソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

    声明:
    この記事はyisu.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。