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

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

基本的な考え方:

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

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

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

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

<?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 クイックソートアルゴリズムを使用する手順の詳細な説明

PHP でプロモーションポスターを生成する手順の詳細な説明

以上がPHP ヒルソートのケース分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。