2015年9月

经典排序算法

  1. 冒泡
$arr = array(3,44,38,5,47,15,36,26,27,2,46,4,19,50,48);
$arr = array(2,3,4,5,15,19,26,27,36,38,44,46,47,48,50);
$times = 0;//记录比较的次数
$len=count($arr);
//控制需要冒泡的轮数
for($i=1;$i<$len;$i++){
  $swapped = false;//[优化]跳出循环之用
  //控制每轮 冒出一个数 需要比较的次数
  for($k=0;$k<$len-$i;$k++){
    $times += 1;
    if($arr[$k]>$arr[$k+1]){
      $tmp=$arr[$k+1];
      $arr[$k+1]=$arr[$k];
      $arr[$k]=$tmp;
      $swapped = true;
    }
  }
  $times += 1;
  if(!$swapped)
    break;
}
echo $times;print_r($arr);

冒泡排序无论代码怎么实现,交换的次数是同样。不同的是,设计良好的算法对于排序良好的输入,进行比较的次数会骤减。

  1. 插入排序
function insert_sort(&$arr){
    $sum = count($arr);
    for($i=1;$i<$sum;$i++){
        $tmp=$arr[$i];
        $key=$i-1;
        while($key>=0 && $tmp<$arr[$key]){
            $arr[$key+1]=$arr[$key];
            $key--;
        }
        $key != $i-1 && $arr[$key+1] = $tmp;//如果有移动,就插入
    }
}
  1. 希尔排序
function shell_sort(&$arr)
{
    if(!is_array($arr)) return;
    $n = count($arr);
    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2))
    {
        for($i=$gap;$i<$n;++$i)
        {
            for($j=$i-$gap;$j>=0 && $arr[$j+$gap]<$arr[$j];$j-=$gap)
            {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+$gap];
                $arr[$j+$gap] = $temp;
            }
        }
    }
}
  1. 选择排序
function selection_sort(&$array){
    $count=count($array);
    for($i=0;$i<$count-1;$i++){
        /*findtheminest*/
        $min=$i;
        echo'$min-->'.$array[$min].'-->';
        for($j=$i+1;$j<$count;$j++){
            //由小到大排列
            if($array[$min]>$array[$j]){
                //表明当前最小的还比当前的元素大
                $min=$j;
                //赋值新的最小的
            }
        }
        echo$array[$min].'coco<br/>';
        /*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
        if($min!=$i){
            $temp=$array[$min];
            $array[$min]=$array[$i];
            $array[$i]=$temp;
        }
    }
}
  1. 快速排序
function quickSort($arr){
    if(count($arr)>1){
        $k=$arr[0];
        $x=array();
        $y=array();
        $size=count($arr);
        for($i=1;$i<$size;$i++){
            if($arr[$i]<=$k){
                $x[]=$arr[$i];
            }elseif($arr[$i]>$k){
                $y[]=$arr[$i];
            }
        }
        $x = quickSort($x);
        $y = quickSort($y);
        return array_merge($x,array($k),$y);
    }else{
        return $arr;
    }
}
  1. 选择排序
function selectSort(&$arr){
    $n = count($arr);
    for($i=0; $i<$n-1; $i++){
        $min_k = $i;
        $min_v = $arr[$i];
        for($j = $i+1; $j<$n; $j++){
            if($arr[$j] < $min_v){
                $min_v = $arr[$j];
                $min_k = $j;
            }
        }
        $arr[$min_k] = $arr[$i];
        $arr[$i] = $min_v;
    }
}