Analysis of the method of implementing Hill sorting algorithm by php

This article describes the method of implementing the Hill sorting algorithm by PHP. Share it for your reference, as follows:

Although various programming languages ​​now have their own powerful sorting library functions, these underlying implementations also utilize these basic or advanced sorting algorithms.

It is still very interesting to understand these complex sorting algorithms, and to understand the exquisiteness of these sorting algorithms~

Hill sort: Hill sort is based on insert sorting, the difference is that the insert sort is adjacent to each other (similar to the case where h=1 in Hill), while Hill sorting is a comparison and replacement of distance h.

In Hill sorting, a constant factor n, the original array is divided into groups, each group consisting of h elements, and there are likely to be extra elements. Of course, every time the cycle is cycled, h is also decreasing (h=h/n). The first cycle starts with the subscript as h. One of Hill's ideas for sorting is to sort it into groups.

To understand these algorithms, it is best to have a diagram. Let's get the code first.

<?php
/**
  * Hill sort
  */
function shell_sort(array $arr){
  // Order $arr in ascending order  $len = count($arr);
  $f = 3;// Definition factor  $h = 1;// Minimum is 1  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // Turn the array into h order    for ($i = $h; $i < $len; $i++){ // Insert a[i] into a[i-h], a[i-2*h], a[i-3*h]... (The key to the algorithm      for ($j = $i; $j >= $h; $j -= $h){
        if ($arr[$j] < $arr[$j-$h]){
          $temp = $arr[$j];
          $arr[$j] = $arr[$j-$h];
          $arr[$j-$h] = $temp;
        }
        //print_r($arr);echo '<br/>'; // Open this line of comments and you can see the situation where each step is replaced      }
    }
    $h = intval($h/$f);
  }
  return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
$shell = shell_sort($arr);
echo '&lt;pre&gt;';
print_r($shell);
/**
*
Array
(
[0] =&gt; -3
[1] =&gt; 1
[2] =&gt; 2
[3] =&gt; 3
[4] =&gt; 4
[5] =&gt; 6
[6] =&gt; 9
[7] =&gt; 13
[8] =&gt; 14
[9] =&gt; 15
[10] =&gt; 17
[11] =&gt; 20
[12] =&gt; 99
)
)
*
*/

PS: Here is a demonstration tool about sorting for your reference:

Online animation demonstration insert/select/bubble/merge/hill/quick sorting algorithm process tool:
http://tools./aideddesign/paixu_ys

For more information about PHP related content, please check out the topic of this site:Summary of php sorting algorithm》、《PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Complete collection of PHP array (Array) operation techniques》、《Summary of usage of php strings》、《Summary of common traversal algorithms and techniques for PHP"and"Summary of PHP mathematical operation skills》

I hope this article will be helpful to everyone's PHP programming.