PHPer面试指南-算法篇

SimpleTriangle 发布于2019-06-28 18:19 / 1469人阅读

摘要：快速排序快速排序是对冒泡排序的一种改进。获取中间数两值相等，返回元素比目标大，查找左部元素比目标小，查找右部查找失败扩展阅读冒泡排序实现快速排序实现各种经典算法常见算法面试篇实现二分查找法

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

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

冒泡排序

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

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($arr) {
    $count = count($arr);
    if(1 >= $count) {
        return arr;
    }

    $base_num = $arr[0]; //选择标的
    $left_array = array();//小于标的
    $right_array = array();//大于标的

    for($i = 1; $i < $count; $i++) {
        if($base_num > $arr[$i]) {
            $left_array[] = $arr[$i];
        } else {
            $right_array[] = $arr[$i];
        }
    }
    //再分别对左边和右边的数组，进行相同的排序处理方式
    $left_array = quick_sort($left_array);
    $right_array = quick_sort($right_array);

    //最终合并
    return array_merge($left_array, array($base_num), $right_array);
}

二分查找（折半查找）

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

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 "查找失败";  
}

扩展阅读

PHP 冒泡排序

php实现快速排序

PHP实现各种经典算法

PHP常见算法-面试篇

php实现二分查找法

GPU云服务器云服务器自然语言处理算法面试字符串算法面试题面试c语言算法编程题 phper

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28156.html

PHPer 面试指南-扩展阅读资源整理

摘要：前端篇收集的前端面试题和答案前端开发面试题史上最全的前端面试题汇总及答案前端工程师手册协议工作原理协议运行机制的概述协议篇原理原理解析的工作原理与的区别理解后端篇年的面试总结垃圾回收机制面向对象设计浅谈说清楚是什么和的区别索引原理及慢查前端篇收集的前端面试题和答案前端开发面试题史上最全的web前端面试题汇总及答案前端工程师手册 HTTP协议：工作原理 SSL/TLS协议运行...

wemall 2019-06-28 18:19 评论0 收藏0
PHPer面试指南-前言

摘要：先说一下面试时的心态，刚入门的程序员，技术实力不高，又大多不善言谈，面试一旦遇到难题，很容易心态失衡惊慌失措语无伦次，最终丢掉了。其实大可不必，心态坦然，是面试必备的一点。本书的 GitHub 地址：https://github.com/todayqq/PH... 作为一位程序员，面试过多次，也面试过很多人，最近又在找工作，总结一下面试经验和面试题，希望可以帮到正在找工作的小伙伴们...

includecmath 2019-06-28 18:20 评论0 收藏0
PHPer面试指南-协议篇

摘要：地址每次面试多多少少都会被问到等等之类协议，协议相关的问题也可以说是面试必备，所以我把这些知识单独收集成了一篇文章。即标志位和标志位均为。发送完毕后，服务器端进入状态。认证服务器对客户端进行认证以后，确认无误，同意发放令牌。 Git 地址：https://github.com/todayqq/PH... 每次面试多多少少都会被问到 HTTP、HTTPS、TCP、Socket、 OAu...

megatron 2019-06-28 18:35 评论0 收藏0
PHPer面试指南-PHP 篇

摘要：本书的地址篇收集了一些常见的基础进阶面试题，基础的面试题不再作答。如何实现持久化持久化，将在内存中的的状态保存到硬盘中，相当于备份数据库状态。相当于备份数据库接收到的命令，所有被写入的命令都是以的协议格式来保存的。本书的 GitHub 地址：https://github.com/todayqq/PH... PHP 篇收集了一些常见的基础、进阶面试题，基础的面试题不再作答。基础篇 ...

stackvoid 2019-06-28 18:19 评论0 收藏0
PHPer面试指南-Web 篇

摘要：扩展阅读收集的前端面试题和答案前端开发面试题史上最全的前端面试题汇总及答案前端工程师手册协议工作原理协议运行机制的概述本书的 GitHub 地址：https://github.com/todayqq/PH... 对于大公司，很少会有全栈工程师这个岗位，全栈是个花哨的词，对于现在比较热门的技术，不论是 Vue 还是 Laravel，只要智商不差，看着文档，都能写出一个 CURD 来，...

cnio 2019-06-28 18:19 评论0 收藏0