希尔排序

基本概念

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法.
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止.

人话(图解shell排序)

1. 数据源[8,3,6,7,4,9,2,5]

2. 初始增量gap=length/2=4

   
   1.jpg

数组被分为四组[8,4], [3,9],[6,2],[7,5],组内比较排序结果为
[4,8], [3,9],[2,6],[5,7]结果集为[4,3,2,5,8,9,6,7]

2. 缩小增量gap=gap/2=2

   
   2.jpg

数组被分会两组[4,2,8,6],[3,5,9,7]组内排序
[2,4,6,8],[3,5,7,9]结果集为[2,3,4,5,6,7,8,9] (巧合已经有序,增量大于1,需要继续缩小增量)

3. 重复第二步gap=gap/2=1

   
   3.jpg

数组被分为一组[2,3,4,5,6,7,8,9],组内排序[2,3,4,5,6,7,8,9],由于增量已经到达1,停止缩小增量输出结果集[2,3,4,5,6,7,8,9]

代码示例

Talk is cheap, show you my code!

<?php

/**
 * 希尔排序
 * @param array $arr
 * @return array
 */
function shellSort(array $arr)
{
    for ($gap = floor(count($arr) / 2); $gap > 0; $gap = floor($gap / 2)) { // 缩小增量
        for ($i = $gap; $i < count($arr); $i++) { // 组内循环排序
            $j = $i;
            while ($j - $gap >= 0 && $arr[$j] < $arr[$j - $gap]) { //完成组内元素一次排序
                swap($arr, $j, $j - $gap);
                $j -= $gap;
            }
        }
        echo implode(',', $arr) . PHP_EOL; // 完成一次增量输出一次结果
    }
    return $arr;
}

/**
 * 交换函数
 * @param array $arr
 * @param int $a
 * @param int $b
 */
function swap(array &$arr, int $a, int $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
shellSort([8,3,6,7,4,9,2,5]);

结论

希尔排序的时间复杂度取决于初始增量的选取,本文所选去的初始增量方式时间复杂度为O(nlog2n)