PHP의 Hill 정렬에 대한 자세한 설명

힐 정렬은 먼저 직접 삽입 정렬을 위해 정렬할 요소의 전체 시퀀스를 여러 하위 시퀀스(특정 "증분"으로 구분된 요소로 구성)로 나눈 다음, 요소가 기본적으로 순서대로 정렬되기 전에 순차적으로 증분을 줄입니다. 증분이 충분히 작은 경우) 모든 요소에 대해 직접 삽입 정렬을 수행합니다. 직접 삽입 정렬은 요소가 기본적으로 정렬되어 있을 때(최상의 경우에 가까움) 매우 효율적이기 때문에 Hill 정렬은 처음 두 방법보다 시간 효율성이 더 높습니다.

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) 이하 동일.

초 간격 = 5 / 2 = 2

정렬 후

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

Th ird 시간 간격 = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

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

네 번째 갭 = 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의 Hill 정렬에 대한 자세한 설명

JS Hill 정렬 및 퀵 정렬 구현 방법

JavaScript 정렬 알고리즘의 Hill 정렬 두 가지 예_기본 지식

위 내용은 PHP의 Hill 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!