PHPer 面试指南-算法篇
32

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

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

  • 冒泡排序

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

function bubble_sort($arr)  
{  
    $count = count($arr);  
    if (0 == $count) {
        return false;  
    }

    for($i = 0; $i < $count; $i++){  
        for($j = 0; $j< $count-1-$i; $j++){
            if($arr[$j] > $arr[$j+1]){
                $temp        = $arr[$j];
                $arr[$j]     = $arr[$j+1];
                $arr[$j+1]   = $temp;
           }
      }
    }  
    return $arr;  
} 

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

  • 快速排序

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

实现思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达到整个序列有序的目的。

简单来说就是:找到当前数组中的任意一个元素(一般选择第一个元素),作为标的,新建两个空数组,遍历这个数组元素,如果数组的值比标的小,那么就放到左边的数组,否则放到右面的数组,然后再对这两个数组进行同样的操作。

function quick_sort(array $list) {
    $len = count($list);
    if ($len <= 1) {
        return $list;
    }
    $pivotValue = $list[0];
    $left = array();
    $right = array();
    for ($i = 1; $i < $len; $i++) { 
        if ($list[$i] < $pivotValue) {
            $left[] = $list[$i];
        }else{
            $right[] = $list[$i];
        }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left, array($pivotValue), $right);
}
  • 二分查找(折半查找)

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

function binSearch($arr, $target){  
    $height = count($arr)-1;  
    $low = 0;  

    while($low <= $height){  
        $mid = floor(($low+$height)/2);//获取中间数

        //两值相等,返回 
        if($arr[$mid] == $target){  
            return $mid; 

        //元素比目标大,查找左部 
        } elseif ($arr[$mid] < $target){
            $low = $mid + 1;  

        //元素比目标小,查找右部
        } elseif ($arr[$mid] > $target){  
            $height = $mid - 1;  
        }  
    }  
    return "查找失败";  
}

扩展阅读

谦虚、自律、胸有成竹、不露城府

本帖由系统于 9个月前 自动加精
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
讨论数量: 8

快排那个好像不对

9个月前

@梦康 这段代码可以直接用来执行,我有确认过,如果有不对的地方,欢迎指正

9个月前

二分查找不太对,以上的代码只有一次二分,实际应该是不断地递归二分

8个月前

@tybalt1991 while循环了

8个月前

用顺序的数组来测试,二分是没问题的,就是开始的时候看注释的左部右部,把我搞乱了,好像注释写反了

8个月前
chenyuanqi

乍一看,快排似乎不支持重复元素哦

8个月前

@chenyuanqi 对的,没错,的确有这个问题,GItHub 之前已修改,这里忘记修改了:joy:

8个月前

你的这些方法都改成引用比较好。

7个月前

  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!