Home >Backend Development >PHP Tutorial >Implementation of PHP Hill (Shell) sorting algorithm (detailed code explanation)

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

藏色散人
藏色散人Original
2019-03-07 10:23:063774browse

Hill (Shell) sorting or Shell method is an in-place comparison sorting. It can be seen as a generalization of bubble sort or insertion 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.

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

Shell sorting example is as follows:

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

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 is unstable: 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:

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

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

<?php
function shell_Sort($my_array)
{
    $x = round(count($my_array)/2);
    while($x > 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(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn