PHP での Hill ソートの詳細な説明

ヒルソートは、直接挿入ソートのために、まずソート対象の要素のシーケンス全体をいくつかのサブシーケンス（特定の「増分」で区切られた要素で構成）に分割し、要素が基本的にソートされる前に増分を連続的に減らします。順序 (増分は十分に小さい) で、すべての要素に対して直接挿入ソートを実行します。直接挿入ソートは、要素が基本的に順序付けされている (最良の場合に近い) 場合に非常に効率的であるため、Hill ソートは最初の 2 つの方法よりも時間効率が高くなります。

n=10 49, 38, 65, 97, 26, 13, 27, 49, 55, 4 の配列を例に挙げます

最初のギャップ = 10 / 2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B

2A 2B

3A 3B

4A 4B

1A、1B、2A、2B などは、同じグループにあることを示します。それらが同じグループにあることを示します。グループの最初のいくつかの要素は、毎回同じデータ グループに直接挿入されます。つまり (49, 13) (38, 27) (65, 49) (97, 55) (26, 4) というように 5 つのグループに分けられ、それぞれのグループをソートすると (13, 4) となります。 49）（27、38）（49、65）（55、97）（4、26）、以下同じ。

2番目のギャップ = 5 / 2 = 2

ソート後

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

Thiギャップの rd 倍 = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

4番目のギャップ = 1 / 2 = 0 ソート後、配列が取得されます:

4 13 26 27 38 49 49 55 65 97

例:

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
    // 将$arr按升序排列
    $len = count($arr);
    $f = 3;// 定义因子
    $h = 1;// 最小为1
    while ($h < intval($len/$f)){
        $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
    }
    while ($h >= 1){  // 将数组变为h有序
    	echo &#39;<br>&#39;.&#39;h:&#39;.$h.&#39;<br>&#39;.&#39;<br>&#39;;
        for ($i = $h; $i < $len; $i++){  // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
        	echo &#39;i:&#39;.$i.&#39;<br>&#39;;
            for ($j = $i; $j >= $h && $arr[$j] < $arr[$j-$h];  $j -= $h){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j-$h];
                $arr[$j-$h] = $temp;
                dump($arr);
            }
        }
        $h = intval($h/$f);
    }
    return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
dump($arr);
$shell = shell_sort($arr);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
function dump($arr)
{
	foreach ($arr as $value) {
		echo $value.&#39; &#39;;
	}
	echo &#39;<br>&#39;;
}

結果:

14 9 1 4 6 -3 2 99 13 20 17 15 3
h:4
i:4
6 9 1 4 14 -3 2 99 13 20 17 15 3
i:5
6 - 3 1 4 14 9 2 99 13 20 17 15 3
i:6
i:7
i:8
6 -3 1 4 13 9 2 99 14 20 17 15 3
i:9
i:10
i: 11
6 -3 1 4 13 9 2 15 14 20 17 99 3
i:12
6 -3 1 4 13 9 2 15 3 20 17 99 14
6 -3 1 4 3 9 2 15 13 20 17 99 14
3 -3 1 4 6 9 2 15 13 20 17 99 14
h:1
i:1
-3 3 1 4 6 9 2 15 13 20 17 99 14
i:2
-3 1 3 4 6 9 2 15 13 20 17 99 14
i:3
i:4
i:5
i:6
-3 1 3 4 6 2 9 15 13 20 17 99 14
-3 1 3 4 2 6 9 15 13 20 17 99 14
-3 1 3 2 4 6 9 15 13 20 17 99 14
-3 1 2 3 4 6 9 15 13 20 17 99 14
i:7
i:8
-3 1 2 3 4 6 9 13 15 20 17 99 14
i:9
i:10
-3 1 2 3 4 6 9 13 15 17 20 99 14
i:11
i:12
-3 1 2 3 4 6 9 13 15 17 20 14 99
-3 1 2 3 4 6 9 13 15 17 14 20 99
-3 1 2 3 4 6 9 13 15 14 17 20 99
-3 1 2 3 4 6 9 13 14 15 17 20 99

rrリー

関連する推奨事項:

JavaScriptでのヒルソートの詳しい説明

JSヒルソートとクイックソートの実装方法

JavaScriptソートアルゴリズムでのヒルソートの2つの例_基礎知識

以上がPHP での Hill ソートの詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。