Detailed explanation of Hill sorting in PHP

Hill sorting is to first divide the entire sequence of elements to be sorted into several subsequences (composed of elements separated by a certain "increment") for direct insertion sorting, and then reduce the increments in sequence and then sort. When the elements in the sequence are basically in order (the increment is small enough), perform a direct insertion sort on all elements. Because direct insertion sorting is very efficient when the elements are basically ordered (close to the best case), Hill sorting has a greater time efficiency than the first two methods.

Take an array 49, 38, 65, 97, 26, 13, 27, 49, 55, 4 with n=10 as an example

The first gap = 10 / 2 = 5

49 38 65 97 26 3 27 49

## 1A 1B

## 2a 2B

# 3A 3B

# 4A 4B

## 5A 5B

## 1A, 1B, 2A, 2B, etc. The same is indicated in the same group. The data is sorted directly by insertion. That is, it is divided into five groups (49, 13) (38, 27) (65, 49) (97, 55) (26, 4). In this way, after each group is sorted, it becomes (13, 49) (27, 38) ( 49, 65) (55, 97) (4, 26), the same below.

Second gap = 5 / 2 = 2

After sorting

13 27 49 55 4 49 38 65 97 26

##1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

The third gap = 2 / 2 = 1

##4 26 13 27 38 49 49 55 97 65

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

The fourth gap = 1 / 2 = 0 After sorting, we get the array:

4 13 26 27 38 49 49 55 65 97

example:

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

Result:

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
)

Related recommendations:

Detailed explanation of Hill sorting in JavaScript

Implementation methods of JS Hill sorting and quick sort

JavaScript sorting algorithm Two examples of Hill sorting_Basic knowledge

The above is the detailed content of Detailed explanation of Hill sorting in PHP. For more information, please follow other related articles on the PHP Chinese website!