php演算法學習記錄

<?php
/** 
* Created by PhpStorm. 
* User: Administrator 
* Date: 2018/4/12 
* Time: 22:22 
*/
header("content-type:text/html;charset=utf-8");
$arr = array(3,5,8,4,9,6,1,7,2);
/** 
* 冒泡排序 
* 思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。 
* 思路：冒泡算法是由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 
* @param $arr * @return mixed *///print_r(insert_sort($arr));function BubbleSort($arr){      
//从小到大排序    
$length = count($arr);    
if($length<=1){        
return $arr;    
}    
for($i=0;$i<$length;$i++){        
for($j=$length-1;$j>$i;$j--){            
if($arr[$j]<$arr[$j-1]){                
$tmp = $arr[$j];                
$arr[$j] = $arr[$j-1];                
$arr[$j-1] = $tmp;            
}            
//另外一种是每次单独拿一个去跟后面的去比较---暂时不知道叫什么            
if ($arr[$j] < $arr[$i]) {                
$temp = $arr[$j];                
$arr[$j] = $arr[$i];                
$arr[$i] = $temp;            
}        
}    
}    
return $arr;}#冒泡算法(另一种写法)function bubbleSort1($arr) {
    $length = count($arr);
        for ($i = 0;$i<$length;$i++) {        
        for ($j = 0;$j<$length-1;$j++) {
        //每次它的极限就是比它此刻小一个的值
                    if ($arr[$j] < $arr[$j + 1]) {                
                    $temp = $arr[$j];               
                    $arr[$j] = $arr[$j + 1];                
                    $arr[$j + 1] = $temp;            
                    }//            
                    if ($arr[$j] > $arr[$i]) {//                
                    $temp = $arr[$j];//                
                    $arr[$j] = $arr[$i];//                
                    $arr[$i] = $temp;//            
                    }        
                    }
                        }    
                        return $arr;}/** 
                        * 快速排序 
                        * 思路： 
                        *      1.选择最前面的值作为枢轴 
                        *      2.定义两个数组 
                        *      3.把比枢轴小的放到左边--比数轴大的放到右边 
                        *      4.再递归使用本函数分别合并两边的结果，最终再把最初的数轴放中间合并返回结果 
                        * @param $arr * @return array    
                        //程序流程    
                        //枢轴为5 left 3,4,1,2  right 8,9,6,7    
                        //left 枢轴为3 left 1,2  right 4 枢轴为8 left6,7  right  9    
                        //左边合并的结果  然后合并上最初的枢轴  再合并生右边合并的结果    
                        //1,2,3,4    5    6,7,8,9 */function QSort($arr){    
                        $length = count($arr);    if($length <=1){        
                        return $arr;    }    
                        $pivot = $arr[0];//枢轴    
                        $left_arr = array();    
                        $right_arr = array();    
                        for($i=1;$i<$length;$i++){//注意$i从1开始0是枢轴        
                        if($arr[$i]<=$pivot){//            
                        array_push($left_arr,$arr[$i]);            
                        $left_arr[] = $arr[$i];       
                        //这种往数组里添加值得方式相对快速        
                        }else{//            
                        array_push($right_arr,$arr[$i]);            
                        $right_arr[] = $arr[$i];      
                        //这种往数组里添加值得方式相对快速        
                        }    
                        }    
                        $left_arr = QSort($left_arr);//递归排序左半部分    
                        $right_arr = QSort($right_arr);//递归排序右半部份    
                        print_r(array_merge($left_arr,array($pivot),$right_arr));    
                        echo "<br/>";    
                        return array_merge($left_arr,array($pivot),$right_arr);//合并左半部分、枢轴、右半部分}
                        /** 
                        * 插入排序 
                        * 思路： 
                        * 将要排序的元素插入到已经 假定排序号的数组的指定位置。 
                        * @param $arr * @return mixed    
                        //程序流程    
                        //第一次进入 $tmp=5 for($j=$i-1;$j>=0;$j--)  
                        如果 5<3 不成立    
                        //第二次  $tmp=8 如果 8<5 不成立    
                        //第三次  $tmp=4 如果 4<8 8和4替换  结果为 3,5,4,8,9,6,1,7,2    
                        //第四次  $tmp=9 如果 9<8 不成立    
                        //       
                        $tmp=6 6<9  3,5,4,8,6,9,1,7,2
                        //1<9 3,5,4,8,6,1,9,7,2
                        //7<9 3,5,4,8,6,1,7,9,2
                        //2<9 3,5,4,8,6,1,7,2,9 */
                        function insert_sort($arr) {    
                        //找到其中一个需要排序的元素    
                        //这个元素 就是从第二个元素开始，到最后一个元素都是这个需要排序的元素    
                        //i循环控制 每次需要插入的元素，一旦需要插入的元素控制好了，    
                        //间接已经将数组分成了2部分，下标小于当前的（左边的），是排序好的序列    
                        for($i=1, $len=count($arr); $i<$len; $i++) {        
                        //获得当前需要比较的元素值。        
                        $tmp = $arr[$i];//        
                        echo "tmp=".$tmp."---";        
                        for($j=$i-1;$j>=0;$j--) {            
                        if($tmp < $arr[$j]) {//                
                        echo "如果".$tmp."<".$arr[$j]."的话。就替换成功";                
                        //发现插入的元素要小，交换位置    //将后边的元素与前面的元素互换                
                        $arr[$j+1] = $arr[$j];                
                        $arr[$j] = $tmp;            
                        } else {//                
                        echo "如果".$tmp."<".$arr[$j]."的话。就替换失败";//                
                        print_r($arr);//                
                        echo "<br/>";                
                        break;            
                        }//            
                        print_r($arr);//            
                        echo "<br/>";        
                        }    
                        }    
                        return $arr;}
                        /** 
                        * 顺序查找 
                        * @param $arr 
                        * @param $key 
                        * @return int 
                        *///$key = 2;
                        //echo "<br/>顺序常规查找{$key}的位置：";
                        //echo SqSearch($arr,$key);
                        function SqSearch($arr,$key){    
                        $length = count($arr);    
                        for($i=0;$i<$length;$i++){        
                        if($key == $arr[$i]){            
                        return $i+1;        
                        }    
                        }    
                        return -1;}
                        /** 
                        *二分查找(必须是一个有序的数组) 
                        * 假设我们的数组是一个递增的数组，首先我们需要找到数组的中间位置. 
                        * 一。要知道中间位置就需要知道起始位置和结束位置，然后取出中间位置的值来和我们的值做对比。 
                        * 二。如果中间值大于我们的给定值，说明我们的值在中间位置之前，此时需要再次二分，
                        因为在中间之前，所以我们需要变的值是结束位置的值，此时结束位置的值应该是我们此时的中间位置。 
                        * 三。反之，如果中间值小于我们给定的值，那么说明给定值在中间位置之后，此时需要再次将后一部分的值进行二分，
                        因为在中间值之后，所以我们需要改变的值是开始位置的值，此时开始位置的值应该是我们此时的中间位置，
                        直到我们找到指定值。    
                        //程序流程    
                        //找6  $mid=4  6==5 6<5  6>5---->让mid+1    
                        // mid=5 return 5+1 位置为6 
                        * @param $arr 
                        * @param $low      从第一个开始找(索引值0) 
                        * @param $high     结束点 (数组的长度) 
                        * @param $key * @return int 
                        *///$key = 6;//echo "二分查找{$key}的位置：";
                        //echo binary_search($arr,0,count($arr),$key);
                        function binary_search($arr,$low,$high,$key){    
                        for($i=$low;$i<=$high;$i++){        
                        $mid = intval(($low+$high)/2);
                        //        echo $mid;  
                        //不够就是不够，不会往上舍取        
                        if($key == $arr[$mid]){            
                        return $mid+1;        
                        }elseif($key<$arr[$mid]){            
                        $high = $mid-1;        
                        }elseif($key>$arr[$mid]){            
                        $low = $mid+1;        
                        }    
                        }//    
                        while($low<=$high){//        
                        $mid = intval(($low+$high)/2);//        
                        if($key == $arr[$mid]){//            
                        return $mid+1;//        
                        }elseif($key<$arr[$mid]){//            
                        $high = $mid-1;//        
                        }elseif($key>$arr[$mid]){//            
                        $low = $mid+1;//        
                        }//    
                        }    
                        return -1;
                        }

               

#

以上是php演算法學習記錄的詳細內容。更多資訊請關注PHP中文網其他相關文章！