Implementation of PHP Hill (Shell) sorting algorithm (detailed code explanation)

Hill (Shell) sorting or Shell method is an in-place comparison sorting. It can be seen as a generalization ofbubble sortorinsertion sort. This method first sorts pairs of elements that are far apart from each other and then gradually closes the gap between the elements to be compared. Starting with elements that are far apart allows you to move some out-of-place elements faster than neighbor swapping.

Shell sorting example is as follows:

The first traversal is "5 sorting" , perform insertion sort on different subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). For example, it changes the subarray (a1, a6, a11) from (62,17,25) to (17,25,62).

Then "3 sort", perform insertion sort on the subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12).

The last time is "1 sort", which is the entire array (a1,...,a12). As shown in the example, the subarrays of the Shell sort operation are initially very short; later they become longer, but they are basically ordered. In both cases, insertion sort works.Hill (Shell) sorting isunstable: it may change the relative order of elements with equal values. It is an adaptive sorting algorithm that performs faster when the input is partially sorted.

The Hill (Shell) sorting graphic is as follows:

Code example of PHP implementing the Hill (Shell) sorting algorithm:

 0) { for($i = $x; $i < count($my_array);$i++){ $temp = $my_array[$i]; $j = $i; while($j >= $x && $my_array[$j-$x] > $temp) { $my_array[$j] = $my_array[$j - $x]; $j -= $x; } $my_array[$j] = $temp; } $x = round($x/2.2); } return $my_array; } $test_array = array(3, 0, 2, 5, -1, 4, 1); echo "原始数组 :\n"; echo implode(', ',$test_array ); echo "\n排序后数组\n:"; echo implode(', ',shell_Sort($test_array)). PHP_EOL;

Output:

原始数组 : 3, 0, 2, 5, -1, 4, 1 排序后数组 :-1, 0, 1, 2, 3, 4, 5

This article is an introduction to the PHP Hill (Shell) sorting algorithm. It is simple and easy to understand. I hope it will be helpful to friends in need!

The above is the detailed content of Implementation of PHP Hill (Shell) sorting algorithm (detailed code explanation). For more information, please follow other related articles on the PHP Chinese website!