<?php
/**
 * 原理：把排序的数据根据增量分成几个子序列，对子序列进行插入排序，
 * 直到增量为1，直接进行插入排序，增量的排序，一般是数组长度的一半，再变为原来增量的一半，直到增量为1
 * 时间复杂度：最差 Θ(n2) 平均时间复杂度 O(log2n)
 * 最差的情况：因为$gap的值不互质(最大公因数不是1)所以导致增量序列没有起到作用
 * 可以使用例如 Hibbrd增量序列
 */

    //生成指定区间不重复数组
    function uniqueRandom($min, $max, $num) {
        $count = 0;
        $return = [];

        while($count < $num) {
            //生成指定数值期间的随机数
            $return[] = mt_rand($min, $max);
            //用两次键值翻转,去除数组中重复的数据项
            $return = array_flip(array_flip($return));
            $count = count($return);
        }
        //再次作一下随机排序
        shuffle($return);
        return $return;
    }

    //希尔排序，插入排序的改进版
    function shellSort(&$arr):void {
        $count = count($arr);
        //希尔增量序列
        for ($gap=intval($count/2); $gap>0; $gap=intval($gap/2)) {
            //插入排序
            for ($p=$gap; $p<$count; $p++) {
                //摸下一张牌
                $temp = $arr[$p];
                for ($i=$p; $i>= $gap && $arr[$i-$gap]>$temp; $i-=$gap) {
                    //移出空位
                    $arr[$i] = $arr[$i - $gap];
                }
                //新牌落位
                $arr[$i] = $temp;
            }
        }

    }

    $arr = uniqueRandom(1, 100000, 5000);
    $start = microtime(true);
    shellSort($arr);
    $end = microtime(true);
    $used = $end - $start;
    echo "insertSort() used $used s" . PHP_EOL;
    echo '<br/>';
    /*
    for ($i = 0; $i < count($arr)/100; $i++) {
        echo $arr[$i] . '<br/>';
    }
    */
    //php内置排序, 性能超过自己写的好多倍~~:()
    $arr = uniqueRandom(1, 100000, 5000);
    $start = microtime(true);
    asort($arr);
    $end = microtime(true);
    $used = $end - $start;
    echo "asort() used $used s" . PHP_EOL;
    echo '<br/>';
?>

insertSort() used 0.011000871658325 s
asort() used 0.0010008811950684 s