ホームページ >バックエンド開発 >Python チュートリアル >Python でヒルソートアルゴリズムを実装する方法
ヒル ソートは、「縮小増分ソート」とも呼ばれ、挿入ソートを最適化することによって生成されるソート アルゴリズムです。その実行のアイデアは、配列内の要素を添え字の増分にグループ化し、要素の各グループを挿入して並べ替え、増分を減らし、増分が 1 に達するまで前の手順を繰り返すというものです。
一般的に言えば、Hill ソートの時間計算量は O(n1.3) ~ O(n2) であり、これは増分サイズに依存します。 Hill ソートの空間計算量は O(1) であり、不安定なソート アルゴリズムです。ヒル ソートを実行する場合、要素の 1 つの移動が複数の要素にまたがる場合があり、これにより複数の移動が相殺され、効率が向上することがあります。
次は、(配列の長さ/2) を初期増分として使用する昇順ヒル ソートです。ソートの各ラウンドの後、増分は半分に減ります。
図 2-28 に示すように、最初の要素から開始して、増分 4 でグループ化します。増分が 4 の場合、グループ内の要素は 2 つだけであることがわかります。そうでない場合、要素の添字は配列の範囲を超えます。
図 2-29 に示すように、グループ内の要素を挿入して並べ替えます。
図 2-30 に示すように、引き続き同じ方法を使用して、グループ内の要素をグループ化、挿入、並べ替えます。彼らが秩序あるように。
配列全体のすべての数値を調べ終わると、このラウンドの並べ替えは終了します。増分を半分に減らし、次の並べ替えラウンドに進みます。
図 2-31 に示すように、増分が 2 の場合、各グループの要素が増加し、グループの総数が減少していることがわかります。各グループを横断するまで、各グループ内の要素の挿入ソートを続けます。
ソートの最終ラウンドは図 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 サイトの他の関連記事を参照してください。