shell排序法

gap為1,2,4,8,16,32...

  $length=rand(8,20);

  for($i=0;$i<$length;$i++)
  $a[]=rand(100,200);

  for($gap=(int)($length/2);$gap>0;$gap=(int)($gap/2)){
   for($i=$gap;$i<$length;$i++){
    for($j=$i;$j>=$gap;$j-=$gap){
     if($a[$j-$gap]>$a[$j]){
      $tmp=$a[$j-$gap];
      $a[$j-$gap]=$a[$j];
      $a[$j]=$tmp;
     }else{
      break;
     }
    }
   }
  }
   
  foreach($a as $num)
  echo $num."\n";

gap為1,4,13,40,121...

  $length=rand(10,20);

  for($i=0;$i<$length;$i++)
  $a[]=rand(100,200);

  for($gap=1;$gap<(int)($length/3);$gap=($gap*3+1))
  ;

  while($gap>0){
   for($i=$gap;$i<$length;$i++){
    for($j=$i;$j>=$gap;$j-=$gap){
     if($a[$j]<$a[$j-$gap]){
      $tmp=$a[$j];
      $a[$j]=$a[$j-$gap];
      $a[$j-$gap]=$tmp;
     }else{
      break;
     }
    }
   }
   $gap=($gap-1)/3;
  }

  foreach($a as $num)
  echo $num."\n";