PHP Hill Sorting Case Analysis

This time I will bring you a case analysis of PHP Hill sorting. What are the precautions when using PHP Hill sorting case? The following is a practical case, let’s take a look.

Basic idea:

Hill sorting refers to recording by a certain increment of the subscript Group, for each The groups use direct insertion sorting. As the increment gradually decreases, each group contains more and more keywords. When the increment decreases to 1, the entire sequence is divided into one group, and the algorithm terminates.

Operation steps:

First take an integer less than n (the number of sequence records) d1 as the first one Incrementally, group all records in the file. All records whose distance is a multiple of d1 are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2 < d1 and repeat the above grouping and sorting until the increment dt=1( dt < d(t-1) ...< ; d2 < d1), that is, until all records are placed in the same group for direct insertion sorting.

This method is essentially a grouping insertion method

Comparison For numbers that are far apart (called increments) so that the numbers can move across multiple elements, a single comparison[2] may eliminate multiple element exchanges. D.L. Shell implemented this idea in 1959 in a sorting algorithm named after him. The algorithm first divides a set of numbers to be sorted into several groups according to a certain increment d, and the subscripts recorded in each group differ by d. Sorts all the elements in each group, and then uses a smaller increment to sort it. Sort again within each group. When the increment is reduced to 1, the entire number to be sorted is divided into one group and the sorting is completed.

Generally, half of the sequence is taken as the increment for the first time, and then halved each time until the increment is 1.

Regarding the method of selecting increments, it is said that the best increment sequence has not been found so far, but there is a strong requirement that the last increment value must be equal to 1.

The sorting process of shell sorting for a given instance

Assume that the file to be sorted has 10 records, and their keywords are:

49, 38, 65, 97, 76, 13, 27, 49, 55, 04.

The values ​​of the incremental sequence are:

5, 3, 1

Algorithm implementation:

<?php
//希尔排序(对直接插入排序的改进)
function ShellSort(array &$arr)
{
  $count = count($arr);
  $inc = $count;  //增量
  do {
    //计算增量
    //$inc = floor($inc / 3) + 1;
    $inc = ceil($inc / 2);
    for ($i = $inc; $i < $count; $i++) {
      $temp = $arr[$i];  //设置哨兵
      //需将$temp插入有序增量子表
      for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
        $arr[$j + $inc] = $arr[$j]; //记录后移
      }
      //插入
      $arr[$j + $inc] = $temp;
    }
    //增量为1时停止循环
  } while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);</p>
<p style="text-align: left;"> Running results: </p>
<pre class="brush:php;toolbar:false">array(10) {
 [0]=>
 int(4)
 [1]=>
 int(13)
 [2]=>
 int(27)
 [3]=>
 int(38)
 [4]=>
 int(49)
 [5]=>
 int(49)
 [6]=>
 int(55)
 [7]=>
 int(65)
 [8]=>
 int(76)
 [9]=>
 int(97)
}

Complexity analysis:

Analysis of the above code , I believe everyone has some understanding that the key to Hill sorting is not to randomly group and sort them individually, but to form a subsequence of records separated by a certain "increment" to achieve jump-like movement, which improves the efficiency of sorting.

The worst case time complexity is O(n^2).

Hill sorting is an unstable sorting.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to the php Chinese website Other related articles!

Recommended reading:

Detailed explanation of the steps to use PHP quick sorting algorithm

Detailed explanation of the steps to generate promotion posters in PHP

The above is the detailed content of PHP Hill Sorting Case Analysis. For more information, please follow other related articles on the PHP Chinese website!