Detaillierte Erklärung der Hill-Sortierung in PHP

Hill-Sortierung unterteilt zunächst die gesamte Sequenz der zu sortierenden Elemente in mehrere Teilsequenzen (bestehend aus durch ein bestimmtes „Inkrement“ getrennten Elementen) für die direkte Einfügungssortierung und reduziert dann sukzessive die Inkremente, bevor die Elemente in der Sequenz sortiert werden grundsätzlich in Ordnung sind (das Inkrement ist klein genug), führen Sie eine direkte Einfügungssortierung für alle Elemente durch. Da die direkte Einfügungssortierung sehr effizient ist, wenn die Elemente grundsätzlich geordnet sind (nahe dem besten Fall), ist die Hill-Sortierung zeiteffizienter als die ersten beiden Methoden.

Nehmen Sie als Beispiel ein Array von n=10 49, 38, 65, 97, 26, 13, 27, 49, 55, 4

Die erste Lücke = 10 / 2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B

2A 3A 2B

3B

4A 4B

5A ist eine Gruppenmarkierung. Die gleichen Zahlen befinden sich in derselben Gruppe. 5B

1A, 1B, 2A, 2B usw. sind gruppiert. Schreiben Sie einen Buchstaben, um anzugeben, um welches Element der Gruppe es sich handelt , jedes Mal für dieselbe Gruppe Die Daten werden direkt durch Einfügen sortiert. Das heißt, es ist in fünf Gruppen unterteilt (49, 13) (38, 27) (65, 49) (97, 55) (26, 4). Auf diese Weise wird es nach dem Sortieren jeder Gruppe zu (13,). 49) (27, 38) ( 49, 65) (55, 97) (4, 26), das Gleiche unten.

Zweite Lücke = 5 / 2 = 2

Nach dem Sortieren

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

Die dritte Lücke = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

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

Die vierte Lücke = 1 / 2 = 0 Nach dem Sortieren wird das Array erhalten:

4 13 26 27 38 49 49 55 65 97

Beispiel:

<?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

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
)

相关 推荐 推荐：

JavaScript中的希尔排序详解

JS希尔排序与快速排序的实现方法

JavaScript排序算法之希尔排序的2个实例_基础知识

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der Hill-Sortierung in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!