4希尔排序

https://www.yduba.com/biancheng-5472542087.html
希尔排序是插入排序的一种，也称缩小增加排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

算法步骤
1. 取增量，一般取数组长度 / 2；
2. 按增量取得一个子数列，对子数列按插入排序的方式处理；
3. 将增量递减，重复1，2步骤；
4. 直至增量均为0，数列已经排好序；

效率分析
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n**2)好一些。

算法稳定性
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n**2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

动图演示


代码实现

<?php
function shellSort(array $numbers=array())
{
    $count = count( $numbers );
    if( $count <= 1 ) return $numbers;
    for($gap = floor($count/2); $gap > 0; $gap = floor($gap/=2))
    {
        for($i=$gap; $i<$count; ++$i)
        {
            for($j = $i-$gap; $j >= 0 && $numbers[$j+$gap] < $numbers[$j]; $j = $j - $gap)
            {
                $temp = $numbers[$j];
                $numbers[$j] = $numbers[$j+$gap];
                $numbers[$j+$gap] = $temp;
            }
        }
    }
    return $numbers;
}