思路

给定一个数组，内容都为数字
外层循环分隔整个数组为多个长度为增量(增量为整数，每次循环除以2)的子序列
外层每分隔一次，内层从增量对应的键开始循环直到数组最后一位
1. 与选择排序同理，如果当前键位 - 增量 (也就是该子序列对应的另一个值)大于当前键位的值，插入当前键位到该子序列对应的另一个值左边(步长为增量)
2. 继续按步长为增量进行累减(当前键位 - 增量 - 增量... )直到当前键位的值大于该子序列对应的另一个值
外层循环结束前已经是一个相对有序的数组了，最后一次循环步长为1，与正常选择排序相同
结束外层循环，得到一个升序数组

代码

<?php

$array = array(3,1,5,6,35,63,23,4,7,2,65);
$count_array = count($array);


for($i = (int)($count_array/2);$i>0;$i=(int)($i/2)){ //循环分隔整个数组为多个长度为增量(增量为整数，每次循环除以2)的子序列
    for($j = (int)$i;$j<$count_array;$j++){ //从增量开始判断
        $index = (int)($j - $i); //步长为增量
        $current = $array[$j];
        while($index >= 0 && $array[$index] > $current){ //相对选择排序只是步长为增量而不为1
            $array[$index + $i] = $array[$index];
            $index = $index - $i;
        }
        $array[$index + $i] = $current;
    }
}

var_dump($array);
?>

算法学习之路 | 希尔排序[Php]

Subscribe

Comments