希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

算法描述

我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  1. 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

希尔排序（Shell Sort） - 图1

代码实现

  1. <?php
  3. class Sorting
  4. {
  5.         /**
  6.      * 希尔排序（非稳定地原地排序算法）
  7.      *
  8.      * @param array $array
  9.      * @return array
  10.      */
  11.     public static function shellSort(array $array): array
  12.     {
  13.         if (empty($array) || count($array) == 1) {
  14.             return $array;
  15.         }
  17.         $length = count($array);
  19.         // $gap = $length >> 1;
  20.         $gap = 1;
  21.         while ($gap < $length / 3) {
  22.             $gap = $gap * 3 + 1;
  23.         }
  25.         for ($gap; $gap > 0; $gap = floor($gap / 3)) {
  26.             for ($i = $gap; $i < $length; $i++) {
  27.                 $temp = $array[$i];
  28.                 for ($j = $i - $gap; $j >= 0 && $array[$j] > $temp; $j -= $gap) {
  29.                     $array[$j + $gap] = $array[$j];
  30.                 }
  31.                 $array[$j + $gap] = $temp;
  32.             }
  33.         }
  35.         return $array;
  36.     }
  37. }

算法分析

  1. 时间复杂度：O(nlogn)
  2. 空间复杂度：O(1)
  3. 非稳定排序
  4. 原地排序