Explication détaillée du tri Hill en PHP

Le tri Hill divise d'abord toute la séquence d'éléments à trier en plusieurs sous-séquences (composées d'éléments séparés par un certain "incrément") pour un tri par insertion directe, puis réduit successivement les incréments avant le tri lorsque les éléments de la séquence. sont fondamentalement en ordre (l'incrément est suffisamment petit), effectuez un tri par insertion directe sur tous les éléments. Étant donné que le tri par insertion directe est très efficace lorsque les éléments sont fondamentalement ordonnés (proche du meilleur des cas), le tri Hill a une plus grande efficacité en termes de temps que les deux premières méthodes.

Prenons comme exemple un tableau de n=10 49, 38, 65, 97, 26, 13, 27, 49, 55, 4

Le premier écart = 10/2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B

2A 3A 2B

3B

4A 4B

5A est une marque de groupe. Les mêmes numéros sont dans le même groupe. 5B

1A, 1B, 2A, 2B, etc. Écrivez une lettre pour indiquer de quel élément du groupe il s'agit. temps pour le même groupe Les données sont triées directement par insertion. Autrement dit, il est divisé en cinq groupes (49, 13) (38, 27) (65, 49) (97, 55) (26, 4). De cette façon, une fois que chaque groupe est trié, il devient (13, 4). 49) (27, 38) ( 49, 65) (55, 97) (4, 26), le même ci-dessous.

Deuxième écart = 5/2 = 2

Après tri

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

Le troisième écart = 2/2 = 1

4 26 13 27 38 49 49 55 97 65

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

Le quatrième écart = 1/2 = 0 Après tri, le tableau est obtenu :

4 13 26 27 38 49 49 55 65 97

Exemple :

<?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个实例_基础知识

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!