您的位置:首页 - 教程 - PHP - 正文
php的一些简单算法程序(冒泡、快速等)

冒泡排序:

function buttle_sort($array) {
        $len=count($array);
        if($len<2){
            return $array;
        }
        for($i=0;$i<$len;$i++){
            $flag = false;//本趟排序开始前,交换标志应为假
            for($j=$len-1;$j>$i;$j--){
                if($array[$j]<$array[$j-1]){
                    $tmp = $array[$j];
                    $array[$j] = $array[$j-1];
                    $array[$j-1] = $tmp;
                    $flag = true;//发生了交换,故将交换标志置为真
                }
            }
        }
        if(!$flag)//本趟排序未发生交换,提前终止算法
            return $array;
        
    }

选择排序

 <?php
 //选择排序
 function selectSort($arr)
 {
     $count = count($arr);
     if ($count < 2) {
         return $arr;
     }
     for ($i = 0; $i < $count; $i ++) {
         $min = $i;
         for($j=$i + 1;$j < $count;$j++){
             if ($arr[$min] > $arr[$j]) {
                 $min = $j; // 找到最小的那个元素的下标
             }
         }
         if ($min != $i) { // 如果下标不是$i 则互换。
             $tmp = $arr[$i];
             $arr[$i] = $arr[$min];
             $arr[$min] = $tmp;
         }
     }
     return $arr;
 }

冒泡排序其实上是和选择排序相比,并无明显差别。都是找到最小的,放到最左端。依次循环解决问题。差别在于冒泡排序的交换位置的次数较多,而选择排序则是找到最小的元素的下标,然后直接和最左端的交换位置。

 

快速排序算法:

 //快速排序
 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;
     }
 }

 二分查找

 /**二分查找:查找一个值在数组中的位置
  * @$arr:操作的数组,前提是按顺序排列
  * @$val:查找的值
  * @$low:查找的起始位置,默认从数组的第一个数找起
  * @hight:查找的结束位置**/
 function binarySearch($arr, $val, $hight, $low=0){    
     while($low <= $hight){        
         $mid = ceil($low + ($hight - $low) / 2);        
         if($arr[$mid] == $val){            
             return $mid;        
         }elseif($arr[$mid] > $val){            
             $hight = $mid -1;        
         }else{            
             $low = $mid +1;        
         }    
     }    
     return -1;
 }

评论: