PHP でのヒルソートアルゴリズムの実装方法の詳細な分析

現在、さまざまなプログラミング言語には独自の強力な並べ替えライブラリ関数がありますが、これらの基礎となる実装でも、これらの基本または高度な並べ替えアルゴリズムが使用されます。これらの複雑なソート アルゴリズムを理解することは非常に興味深いものです。この記事では、主に PHP でヒル ソート アルゴリズムを実装する方法を紹介し、ヒル ソートの原理を簡単に説明し、サンプルの形式でヒル ソートを実装する PHP の具体的な操作スキルを分析します。友達がそれを参照できるようにする必要があります。すべての人に役立つことを願っています。

ヒル ソート (シェル ソート): ヒル ソートは挿入ソートに基づいていますが、違いは、挿入ソートが隣接するものの比較 (Hill の h=1 の場合と同様) であるのに対し、ヒル ソートは距離 h の比較であることです。そして交換します。

ヒルソートにおける定数因数n、元の配列はグループに分割され、各グループはh個の要素で構成され、冗長な要素が存在する可能性があります。もちろん、ループするたびに h も減少します (h=h/n)。最初のサイクルはインデックス h から始まります。ヒルソーティングのアイデアの 1 つは、グループに分けて分類することです。

これらのアルゴリズムを理解するには、図を理解するのが最善です。コードから始めましょう。

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
  // 将$arr按升序排列
  $len = count($arr);
  $f = 3;// 定义因子
  $h = 1;// 最小为1
  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // 将数组变为h有序
    for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
      for ($j = $i; $j >= $h; $j -= $h){
        if ($arr[$j] < $arr[$j-$h]){
          $temp = $arr[$j];
          $arr[$j] = $arr[$j-$h];
          $arr[$j-$h] = $temp;
        }
        //print_r($arr);echo &#39;<br/>&#39;; // 打开这行注释，可以看到每一步被替换的情形
      }
    }
    $h = intval($h/$f);
  }
  return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
$shell = shell_sort($arr);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
/**
*
Array
(
[0] => -3
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 6
[6] => 9
[7] => 13
[8] => 14
[9] => 15
[10] => 17
[11] => 20
[12] => 99
)
)
*
*/

皆さんは学びましたか？急いで試してみてください。

関連する推奨事項:

並べ替えアルゴリズムの詳細な説明

JS_javascriptスキルによって実装されたカウント並べ替えおよび基数並べ替えアルゴリズムの例

JavaScriptで一般的に使用される基本的な並べ替えアルゴリズムの分析例

以上がPHP でのヒルソートアルゴリズムの実装方法の詳細な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。