Detailed analysis of the method of implementing Hill sorting algorithm in PHP

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. This article mainly introduces the method of implementing Hill sorting algorithm in PHP, briefly explains the principle of Hill sorting, and analyzes the specific operation skills of PHP implementing Hill sorting in the form of examples. It needs Friends can refer to it, I hope it can help everyone.

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 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
)
)
*
*/

Have you all learned it? Hurry up and give it a try.

Related recommendations:

Detailed explanation of sorting algorithm

JS implementation of counting sorting and radix sorting algorithm examples_javascript skills

Example analysis of basic commonly used sorting algorithms in JavaScript

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