一、概述

希尔排序，也被称为“缩小增量排序”。

1、基本原理

　　希尔排序中一个常数因子 n，原数组被分成各个小组，每个小组由 h 个元素组成，很可能会有多余的元素。当然每次循环的时候，h 也是递减的（h=h/n）。第一次循环就是从下标为 h 开始。希尔排序的一个思想就是，分成小组去排序。

　

　　

二、PHP 代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 希尔排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        $arrayLen = count($array);
        $f = 3; // 定义因子
        $h = 1; // 定义每个小组元素构成数
        while ($h < $arrayLen / $f) {
            $h = $f * $h + 1;
        }
        while ($h >= 1) {
            for ($i = $h; $i < $arrayLen; $i++){
                for ($k = $i; $k >= $h; $k -= $h){
                    if ($array[$k] < $array[$k - $h]){
                        $temp = $array[$k];
                        $array[$k] = $array[$k - $h];
                        $array[$k - $h] = $temp;
                    }
                }
            }
            $h = intval($h / $f);
        }
        return $array;
    }

}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
$arrObject = new TestCase();
// 执行排序
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

// 结果
3 15 15 19 20 22 24 36 36 64 77 95

　

三、算法性能分析

最好情况：T(n) = O(nlogn)

最差情况：T(n) = O(nlogn)

平均情况：T(n) = O(nlogn)