php经典算法

admin 发表于 [PHP] 分类,标签: PHP代码 算法
0
   1.冒泡算法,排序算法,由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序
$arr=array(199,132,2,456,23,689,234,123,235,89,456,890);
echo '<pre>';
var_dump($arr);
echo '</pre>';
function bubbleSort($arr,$orderby='asc'){
    for($i=0,$len=count($arr); $i<$len; $i++){
	for($j=$len-1; $j>$i; $j--){
	    if(($orderby=='asc' && $arr[$j]<$arr[$j-1]) || ($orderby=='desc' && $arr[$j]>$arr[$j-1])){
		$tmp=$arr[$j];
		$arr[$j]=$arr[$j-1];
		$arr[$j-1]=$tmp;
	    }
	}
    }
}
echo '<pre>';
var_dump(bubbleSort($arr));
echo '</pre>';


  
     2.快速排序,
     快速排序(Quicksort)是对冒泡排序的一种改进。
     由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,
     其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,
     整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    function quickSort($arr){
        $len = count($arr);
        if($len <= 1) {
            return $arr;
        }
        $key = $arr[0];
        $left_arr    = array();
        $right_arr    = array();

        for($i=1; $i<$len; $i++){
            if($arr[$i] <= $key){
                $left_arr[] = $arr[$i];
            } else {
                $right_arr[] = $arr[$i];
            }
        }

        $left_arr    = quickSort($left_arr);
        $right_arr    = quickSort($right_arr);
        return array_merge($left_arr, array($key), $right_arr);
    }


     3.选择排序
     每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
     顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
    function select_sort($arr){
        $count = count($arr);
        for($i=0; $i<$count; $i++){
            for($j=$i+1; $j<$count; $j++){
                if ($arr[$i] > $arr[$j]){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                }
            }
        }
        return $arr;
    }

     4.插入排序
    从第一个元素开始,该元素可以认为已经被排序
    取出下一个元素,在已经排序的元素序列中从后向前扫描
    如果该元素(已排序)大于新元素,将该元素移到下一位置
    重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    将新元素插入到下一位置中
    重复步骤2
    
    function insert_sort($arr){
        $count = count($arr);
        for($i=1; $i<$count; $i++){
            $tmp = $arr[$i];
            $j = $i - 1;
            while($arr[$j] > $tmp){
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
                $j--;
            }
        }
        return $arr;
    }

    $arr = array(49,38,65,97,76,13,27);
    print_r(insert_sort($arr));


 
 
5、归并排序
function Merge(&$arr, $left, $mid, $right) {
  $i = $left;
  $j = $mid + 1;
  $k = 0;
  $temp = array();
  while ($i <= $mid && $j <= $right)
  {
    if ($arr[$i] <= $arr[$j])
      $temp[$k++] = $arr[$i++];
    else
      $temp[$k++] = $arr[$j++];
  }
  while ($i <= $mid)
    $temp[$k++] = $arr[$i++];
  while ($j <= $right)
    $temp[$k++] = $arr[$j++];
  for ($i = $left, $j = 0; $i <= $right; $i++, $j++)
    $arr[$i] = $temp[$j];
}
 
function MergeSort(&$arr, $left, $right)
{
  if ($left < $right)
  {
    $mid = floor(($left + $right) / 2);
    MergeSort($arr, $left, $mid);
    MergeSort($arr, $mid + 1, $right);
    Merge($arr, $left, $mid, $right);
  }
}


6、二分查找-递归
function bin_search($arr,$low,$high,$value) {
    if($low>$high)
        return false;
    else {
        $mid=floor(($low+$high)/2);
        if($value==$arr[$mid])
            return $mid;
        elseif($value<$arr[$mid])
            return bin_search($arr,$low,$mid-1,$value);
        else
            return bin_search($arr,$mid+1,$high,$value);
    }
}


7、二分查找-非递归    
function bin_search($arr,$low,$high,$value) {
    while($low<=$high) {
        $mid=floor(($low+$high)/2);
        if($value==$arr[$mid])
            return $mid;
        elseif($value<$arr[$mid])
            $high=$mid-1;
        else
            $low=$mid+1;
    }
    return false;
}


8、快速排序
function quick_sort($arr) {
    $n=count($arr);
    if($n<=1)
        return $arr;
    $key=$arr[0];
    $left_arr=array();
    $right_arr=array();
    for($i=1;$i<$n;$i++) {
        if($arr[$i]<=$key)
            $left_arr[]=$arr[$i];
        else
            $right_arr[]=$arr[$i];
    }
    $left_arr=quick_sort($left_arr);
    $right_arr=quick_sort($right_arr);
    return array_merge($left_arr,array($key),$right_arr);
}

   

 

 

« 上一篇:PHP对称加密算法类 php概率算法:下一篇 »

发表我的评论