手记

希尔排序学习及PHP实现

在看希尔排序时比较难以理解,并且没有看懂是如何排出来的
https://visualgo.net/zh 也没有这种排序
于是使用php写了代码实现并将每一步打印出来,总算看明白排序的过程了
虽然还是不懂这个原理

上代码

<?php
function ss($arr){
    $n=count($arr);
    $h=1;
    while($h<$n/3)$h=3*$h+1;
    while($h>=1){
        echo "h值为:".$h."\n";
        for($i=$h;$i<$n;$i++){
            for ($j=$i; $j>=$h && less($arr,$j,$j-$h); $j-=$h) { 
                    exch($arr,$j,$j-$h);
            }
        }
        $h=(int)($h/3);
    }
}
function less($arr,$a,$b){
  echo cs()."比较了:键位j<b>".$a.' '.$arr[$a]."</b> 和 键位j-h<b>".$b.' '.$arr[$b]."</b>,结果".$arr[$a]."比较".($arr[$a]<$arr[$b]?"小":"大")."\n";
  return $arr[$a]<$arr[$b]?true:false;
}
function exch(&$arr,$a,$b){
    $c=$arr[$a];
    $arr[$a]=$arr[$b];
    $arr[$b]=$c;
    echo "交换了:".$a.' '.$arr[$a]." 和 ".$b.' '.$arr[$b].",当前顺序".format($arr,$a,$b)."\n";
}
function cs(){
    static $c=0;
    return "第<b>".$c++ ."</b>步:";
}
function format($arr,$a,$b){
    $res ='';
    foreach ($arr as $k => $v) {
        if($k==$a){
            $res .=" <b>".$v."</b>";
        }else if($k==$b){
            $res .=" <b>".$v."</b>";
        }else{
            $res .=" ".$v;
        }
    }
    return $res;
}
$arr='shellsortexample';
$arr=str_split($arr);
echo "<pre>";
echo "初始数组".implode(' ',$arr)."\n";
$d=ss($arr);
?>
<style type="text/css">
    b{
        color:red;
    }
</style>

部分结果截图

0人推荐
随时随地看视频
慕课网APP