PHP ヒルソートのケース分析-PHPチュートリアル-php.cn

PHP ヒルソートのケース分析

php中世界最好的语言

リリース： 2023-03-26 06:20:01

オリジナル

1980 人が閲覧しました

今回は、PHP Hill ソートの事例分析をお届けします。PHP Hill ソートの事例を使用する際の注意事項は何ですか? 以下は実際の事例です。

基本的な考え方:

ヒルソートは、添字の一定の増分でレコードをグループ化することを指します。増分が徐々に減少するにつれて、各グループに含まれるキーワードが増えていきます。、増分が 1 に減少すると、シーケンス全体が 1 つのグループに分割され、アルゴリズムは終了します。

操作手順:

まず、ファイル内のすべてのレコードをグループ化するための最初の増分として、n (シーケンスレコードの数) より小さいinteger

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);

ログイン後にコピー

実行結果:

array(10) {
 [0]=>
 int(4)
 [1]=>
 int(13)
 [2]=>
 int(27)
 [3]=>
 int(38)
 [4]=>
 int(49)
 [5]=>
 int(49)
 [6]=>
 int(55)
 [7]=>
 int(65)
 [8]=>
 int(76)
 [9]=>
 int(97)
}

ログイン後にコピー

複雑性分析:

合格上記のコードの分析から、Hill ソートの鍵は、ランダムにグループ化して個別にソートするのではなく、特定の「増分」によって区切られたレコードのサブシーケンスを形成して、ジャンプのような順序を達成することであることを誰もがすでに理解していると思います。移動するので仕分け効率が上がります。

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

O(n^2)

です。

ヒルソートは不安定なソートです。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイト

その他の

関連記事に注目してください。

推奨読書:

PHP クイックソートアルゴリズムを使用する手順の詳細な説明