PHP sorting algorithm Shell Sort (Shell Sort)

This article mainly introduces the PHP sorting algorithm Shell Sort. It analyzes the principles, implementation methods and related precautions of Shell Sort in detail in the form of examples. Friends in need can refer to it

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

Basic idea:

Hill sorting refers to grouping records by a certain increment of the subscript , use direct insertion sort for each group. 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 d1 less than n (the number of sequence records) as the first increment, and add the All records are grouped. 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);

Run result:

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:

Through the analysis of the above code, I believe everyone has some understanding that the key to Hill sorting is not to randomly group them and then sort them individually, but to separate them by a certain distance. The "incremental" records form a subsequence 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.

This article is referenced from "Dahua Data Structure". It is only recorded here for future reference. Please don't criticize!

Related recommendations:

PHP sorting algorithm series insertion sort example sharing

# #

The above is the detailed content of PHP sorting algorithm Shell Sort (Shell Sort). For more information, please follow other related articles on the PHP Chinese website!