ホームページ > 記事 > バックエンド開発 > PHPソートアルゴリズムシェルソート（Shell Sort）

PHPソートアルゴリズムシェルソート（Shell Sort）

不言オリジナル: 2018-04-20 12:45:261708ブラウズ

この記事では、主に PHP のソートアルゴリズムであるシェルソートを紹介します。シェルソートの原理、実装方法、および関連する注意事項をサンプルの形式で詳細に分析します。必要な方は、この記事の例を参照してください。アルゴリズムシェルソート。参考のために皆さんと共有してください。詳細は次のとおりです:

基本的な考え方: ヒルソートとは、レコードが添字の特定の増分によってグループ化され、各グループに対して直接挿入ソートが使用されることを意味します。増分が徐々に減少し、各グループに含まれるキーワードの数が 1 に減少すると、シーケンス全体が 1 つのグループに分割され、アルゴリズムは終了します。

操作手順: まず、n (シーケンスレコードの数) より小さい整数 d1 を最初の増分として取り、ファイル内のすべてのレコードをグループ化します。距離が d1 の倍数であるすべてのレコードは、同じグループに配置されます。まず各グループ内で直接挿入ソートを実行し、次に 2 番目の増分 d2

このメソッドは本質的にグループ化された挿入メソッドです

遠く離れた数値を比較するため、数値が次のようになります。移動時に複数の要素にまたがる場合、比較 [2] を実行すると、複数の要素の交換が不要になる場合があります。 D.L. シェルは 1959 年にこのアイデアを、彼の名前にちなんで名付けられた並べ替えアルゴリズムに実装しました。このアルゴリズムでは、まず、ソート対象の数値のセットを特定の増分 d に従っていくつかのグループに分割し、各グループに記録されている添え字が d ずつ異なるように、各グループ内のすべての要素をソートしてから、より小さい増分を使用してソートします。各グループ内で再度並べ替えます。増分が 1 に減少すると、ソート対象の数値全体が 1 つのグループに分割され、ソートが完了します。

通常、最初はシーケンスの半分が増分として取られ、その後は増分が 1 になるまで毎回半分になります。

増分を選択する方法に関しては、これまでのところ最良の増分シーケンスは見つかっていないと言われていますが、最後の増分値は 1 に等しくなければならないという強い要件があります。

特定のインスタンスのシェルソートのソートプロセス

ソートされるファイルに 10 個のレコードがあり、それらのキーワードが次のとおりであると仮定します:

49、38、65、97、76、13、27、49、 55、04。

インクリメンタルシーケンスの値:

5, 3, 1

アルゴリズム実装:

<?php
//希尔排序(对直接插入排序的改进)
function ShellSort(array &$arr)
{
  $count = count($arr);
  $inc = $count;  //增量
  do {
    //计算增量
    //$inc = floor($inc / 3) + 1;
    $inc = ceil($inc / 2);
    for ($i = $inc; $i < $count; $i++) {
      $temp = $arr[$i];  //设置哨兵
      //需将$temp插入有序增量子表
      for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
        $arr[$j + $inc] = $arr[$j]; //记录后移
      }
      //插入
      $arr[$j + $inc] = $temp;
    }
    //增量为1时停止循环
  } while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);

演算結果:

りー

複雑度分析: 上記のコードの分析を通じて、ヒルソートの鍵はランダムにグループ化して個別にソートするのではなく、特定の「インクリメント」を実現することでジャンプのような動きを実現し、仕分け効率を向上させます。

最悪の場合の時間計算量は

O(n^2)

です。ヒルソーティングは不安定なソーティングです。

この記事は「Dahua データ構造」から参照されています。将来の参考のためにここに記録されているだけです。批判しないでください。

PHPソートアルゴリズムシェルソート（Shell Sort）

関連記事