PHP面试题之算法解析，php试题解析_PHP教程-php教程-PHP中文网

PHP面试题之算法解析，php试题解析

首页

后端开发

php教程

PHP面试题之算法解析，php试题解析_PHP教程

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jul 12, 2016 am 09:07 AM

面试题

PHP面试题之算法解析，php试题解析

面试中经常被问到会什么算法,这里整合一些常见的算法及它们的实现原理.下面的例子都是经过测试可用的,如果有什么问题请告知!!

本人小白,如果有更好的实现方式,敬请赐教,感激不尽!!!!

冒泡排序,快速排序,选择排序,二分法查找,快速查找

<span>/*<span>* 
* 冒泡排序
* 相邻2数比较,小的在前,大的在后
* 数组有几个元素,就要比较几轮 $i
* 每轮需要比较的次数为,数组元素个数-已比较的次数 $j
* @param   array  <span><span>$array 要操作的数组</span></span>
* @return  array  <span><span>$array 返回的数组</span></span>
<span>*/
<span>function bubbleSort<span>(</span><span>$array<span>)
{
        <span>$cnt = <span>count<span>(</span><span>$array<span>);
        <span>for(<span>$i = 0; <span>$i < <span>$cnt ; <span>$i++<span>){
                <span>for(<span>$j = 0 ; <span>$j < (<span>$cnt-<span>$i-1) ; <span>$j++<span>){
                        <span>if(<span>$array[<span>$j] > <span>$array[<span>$j+1<span>]){
                                <span>$temp = <span>$array[<span>$j<span>];
                                <span>$array[<span>$j] = <span>$array[<span>$j+1<span>];
                                <span>$array[<span>$j+1] = <span>$temp<span>;
                        }
                }
        }
        <span>return <span>$array<span>;
}<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>

登录后复制

<span>/*</span><span>*
* 快速排序
* 递归实现
* 获取数组第一个数,循环使后面的数与其比较,
* 比其小的放在一个数组中,比其大的放在一个数组中
* 将2个数组递归调用,直到最终数组元素小于等于1时,没有可以比较的元素
* 通过array_merge函数,将比较的数组按大小顺序合并然后一层一层的return出去,最终实现从小到大排序
* @param array $array 要操作的数组
* @return array $array 返回的数组
</span><span>*/</span>

<span>function</span> quickSort(<span>$array</span><span>)
{
        </span><span>if</span>(<span>count</span>(<span>$array</span>) <= 1 ) <span>return</span> <span>$array</span><span>;
        </span><span>$key</span> = <span>$array</span>[0<span>];
        </span><span>$left_arr</span> = <span>array</span><span>();
        </span><span>$right_arr</span> = <span>array</span><span>();
        </span><span>for</span> (<span>$i</span>=1;<span>$i</span><<span>count</span>(<span>$array</span>);<span>$i</span>++<span>){
                </span><span>if</span>(<span>$array</span>[<span>$i</span>] <= <span>$key</span><span>){
                        </span><span>$left_arr</span>[] = <span>$array</span>[<span>$i</span><span>];
                }</span><span>else</span><span>{
                        </span><span>$right_arr</span>[] = <span>$array</span>[<span>$i</span><span>];
                }
        }

        </span><span>$left_arr</span> = quickSort(<span>$left_arr</span><span>);
        </span><span>$right_arr</span> = quickSort(<span>$right_arr</span><span>);
        </span><span>return</span> <span>array_merge</span>(<span>$left_arr</span>,<span>array</span>(<span>$key</span>),<span>$right_arr</span><span>);

}</span>

登录后复制

<span>/*</span><span>*
* 选择排序
* 2层循环
* 第一层逐个获取数组的值 $array[$i]
* 第二次遍历整个数组与$array[$i]比较($j=$i+1已经比较的,不再比较,减少比较次数)
* 如果比$array[$i]小,就交换位置
* 这样一轮下来就可以得到数组中最小值
* 以此内推整个外层循环下来就数组从小到大排序了
* @param array $array 要比较的数组
* @return array $array 从小到大排序后的数组
</span><span>*/</span>

<span>function</span> selectSort(<span>$array</span><span>){
        </span><span>$cnt</span> = <span>count</span>(<span>$array</span><span>);
        </span><span>for</span>(<span>$i</span>=0;<span>$i</span><<span>$cnt</span>;<span>$i</span>++<span>){
                </span><span>for</span>(<span>$j</span>=(<span>$i</span>+1);<span>$j</span><<span>$cnt</span>;<span>$j</span>++<span>){
                        </span><span>if</span>(<span>$array</span>[<span>$i</span>]><span>$array</span>[<span>$j</span><span>]){
                                </span><span>$tmp</span> = <span>$array</span>[<span>$i</span><span>];
                                </span><span>$array</span>[<span>$i</span>] = <span>$array</span>[<span>$j</span><span>];
                                </span><span>$array</span>[<span>$j</span>] = <span>$tmp</span><span>;
                        }
                }
        }
        </span><span>return</span> <span>$array</span><span>;
}</span>

登录后复制

<span>/*</span><span>*
* 二分法查找一个值在数组中的位置
* @param array $array 操作的数组
* @param void $val 要查找的值
* @return int $mid 返回要查找的值在数组中的索引,如果不存在返回-1
</span><span>*/</span>

<span>function</span> binarySearch(<span>$array</span>,<span>$val</span><span>)
{
        </span><span>$cnt</span> = <span>count</span>(<span>$array</span><span>);
        </span><span>$low</span> = 0<span>;
        </span><span>$high</span> = <span>$cnt</span> - 1<span>;
        </span><span>while</span> (<span>$low</span> <= <span>$high</span><span>){
                </span><span>$mid</span> = <span>intval</span>((<span>$low</span> + <span>$high</span>)/2<span>);
                </span><span>if</span>(<span>$array</span>[<span>$mid</span>] == <span>$val</span><span>){
                        </span><span>return</span> <span>$mid</span><span>;
                }

                </span><span>if</span>(<span>$array[$mid]</span> < <span>$val</span><span>){
                        </span><span>$low</span> = <span>$mid</span> + 1<span>;
                }

                </span><span>if</span>(<span>$array[$mid]</span> > <span>$val</span><span>){
                        </span><span>$high</span> = <span>$mid</span> - 1<span>;
                }
        }

        </span><span>return</span> -1<span>;
}</span>

登录后复制

<span>/*</span><span>*
* 顺序查找(最简单,效率低下)
* 通过循环数组查找要的值
* @param array $array 要操作的数组
* @param void $val  要查找的值
* @return int 如果存在,返回该值在数组中的索引,否则返回-1
</span><span>*/</span>

<span>function</span> seqSch(<span>$array</span>,<span>$val</span><span>)
{
        </span><span>for</span>(<span>$i</span>=0;<span>$i</span><<span>count</span>(<span>$array</span>);<span>$i</span>++<span>){
                </span><span>if</span>(<span>$array</span>[<span>$i</span>] == <span>$val</span><span>)
                        </span><span>break</span><span>;
        }

        </span><span>if</span>(<span>$i</span> < <span>count</span>(<span>$array</span><span>)){
                </span><span>return</span> <span>$i</span><span>;
        }</span><span>else</span><span>{
                </span><span>return</span> -1<span>;
        }
}</span>

登录后复制

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

免费脱衣服图片

Clothoff.io

AI脱衣机

AI Hentai Generator

免费生成ai无尽的。

显示更多

热工具

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里

7480

CakePHP 教程

1377

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

五个常见的Go语言面试题及解答 Jun 01, 2023 pm 08:10 PM

作为近年来备受热捧的一门编程语言，Go语言已经成为众多公司与企业的面试热点。对于Go语言初学者而言，在面试过程中遇到相关问题时，如何回答是一个值得探讨的问题。下面列举五个常见的Go语言面试题及解答，供初学者参考。请介绍一下Go语言的垃圾回收机制是如何工作的？Go语言的垃圾回收机制基于标记-清除算法和三色标记算法。当Go程序中的内存空间不够用时，Go垃圾回收器