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

アルゴリズムの説明

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

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

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

ステップ 1:

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

ステップ 2:

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

3 番目のステップ:

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

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

ステップ 4:

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

5 番目のステップ:

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

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

コードの実装

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 サイトの他の関連記事を参照してください。