An explanation of how to implement Hill sorting algorithm in PHP

This article mainly introduces the method of implementing Hill sorting algorithm in PHP, briefly explains the principle of Hill sorting, and analyzes the specific operating skills of PHP implementing Hill sorting in the form of examples. Friends in need can refer to the following

The example in this article describes the method of implementing Hill sorting algorithm in PHP. Share it with everyone for your reference, the details are as follows:

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

It is very interesting to understand these complex sorting algorithms and experience the subtlety of these sorting algorithms~

Hill sorting (shell sort): Hill sorting is based on insertion sorting, the difference is that insertion Sorting is a comparison of adjacent ones (similar to the case of h=1 in Hill), while Hill sorting is a comparison and replacement of distance h.

In Hill sorting, with a constant factor n, the original array is divided into groups. Each group consists of h elements, and there may be redundant elements. Of course, h also decreases each time it is looped (h=h/n). The first cycle starts from index h. One idea of ​​Hill sorting is to divide into groups to sort.

To understand these algorithms, it is best to have a diagram. Let’s start with the code.

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
  // 将$arr按升序排列
  $len = count($arr);
  $f = 3;// 定义因子
  $h = 1;// 最小为1
  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // 将数组变为h有序
    for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
      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 &#39;<br/>&#39;; // 打开这行注释，可以看到每一步被替换的情形
      }
    }
    $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 &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
/**
*
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
)
)
*
*/

##Articles you may be interested in:

An explanation of how PHP uses custom keys to encrypt and decrypt data

An example of a simple four-arithmetic arithmetic calculator function implemented by PHP

Explanation on how to implement an unfixed number of parameters in Laravel routing

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