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

Posted ·431 Views·670 Words

思路

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

 

代码

<?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);
?>

Comment

Leave a comment to join the discussion