• 扩展阅读

    本书的 GitHub 地址：https://github.com/todayqq/PHPerInterviewGuide

    算法可以说是大厂的必考题，对于算法，一定要理解其中的精髓、原理。

    • 冒泡排序

    冒泡排序的原理：一组数据，比较相邻数据的大小，将值小数据在前面，值大的数据放在后面。

    1. function bubble_sort($arr)  
    2. {  
    3.     $count = count($arr);  
    4.     if (0 == $count) {
    5.         return false;  
    6.     }
    8.     for($i = 0; $i < $count; $i++){  
    9.         for($j = 0; $j< $count-1-$i; $j++){
    10.           　　if($arr[$j] > $arr[$j+1]){
    11.               　　$temp        = $arr[$j];
    12.               　　$arr[$j]     = $arr[$j+1];
    13.               　　$arr[$j+1]   = $temp;
    14.          　　}
    15.    　　 }
    16.     }  
    17.     return $arr;  
    18. }

    这样的一个数组 array(6, 3, 8, 2, 9, 1)，排序过程是怎样的？细节问题不在过多论述，有兴趣可以从扩展阅读中寻找答案。

    • 快速排序

    快速排序是对冒泡排序的一种改进。

    实现过程是：

    1. 先从数列中取出一个数作为基准数。
    2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
    3. 再对左右区间重复第二步，直到各区间只有一个数。
    1. function quick_sort(array $list) {
    2.     $len = count($list);
    3.     if ($len <= 1) {
    4.         return $list;
    5.     }
    6.     $pivotValue = $list[0];
    7.     $left = array();
    8.     $right = array();
    9.     for ($i = 1; $i < $len; $i++) { 
    10.         if ($list[$i] < $pivotValue) {
    11.             $left[] = $list[$i];
    12.         }else{
    13.             $right[] = $list[$i];
    14.         }
    15.     }
    16.     $left = quick_sort($left);
    17.     $right = quick_sort($right);
    18.     return array_merge($left, array($pivotValue), $right);
    19. }
    • 二分查找（折半查找）

    实现思想：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记 录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

    1. function binSearch($arr, $target){  
    2.     $height = count($arr)-1;  
    3.     $low = 0;  
    5.     while($low <= $height){  
    6.         $mid = floor(($low+$height)/2);//获取中间数
    8.         //两值相等，返回 
    9.         if($arr[$mid] == $target){  
    10.             return $mid; 
    12.         //元素比目标大，查找左部 
    13.         } elseif ($arr[$mid] < $target){
    14.             $low = $mid + 1;  
    16.         //元素比目标小，查找右部
    17.         } elseif ($arr[$mid] > $target){  
    18.             $height = $mid - 1;  
    19.         }  
    20.     }  
    21.     return "查找失败";  
    22. }

    扩展阅读

    • PHP 冒泡排序
    • php四种基础算法
    • PHP实现各种经典算法
    • PHP常见算法-面试篇
    • php实现二分查找法