文档章节

【PHP面试题】通俗易懂的两个面试必问的排序算法讲解:冒泡排序和快速排序

o
 osc_n6euf5h6
发布于 2019/03/19 23:59
字数 1137
阅读 27
收藏 0

精选30+云产品,助力企业轻松上云!>>>

又到了金三银四找工作的时间,相信很多开发者都在找工作或者准备着找工作了。一般应对面试,我们无可厚非的去刷下面试题。对于PHPer来说,除了要熟悉自己所做的项目,还有懂的基本的算法。下面来分享下PHP面试中常会问到的算法:冒泡排序和快速排序

 

冒泡排序:一一对比排序

基本思想:

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。

 

图解:

 

1.第一次:拿着数组的第一个元素,分别从第二个元素开始比较,如果前面的元素比后面的元素大,则交换两个元素,得到较大的这个值,继续向后比较,直到数组元素的最后,实现一次冒泡(冒泡一次,就得到当前“剩余”数组的最大值,并且放到数组的“最后面”)

2.第二次开始,还是从第一个元素开始比较,但是只比较到数组长度要-1位置,并且每次的比较次数都依次-1

3.后面重复比较,直到最后没有需要一堆数字需要比较

代码:

 1         $arr = array(3,2,6,0,1,4,7);
 2         //因为排序需要每次将一个元素与数组的其他元素进行比较,所以需要两层循环来控制
 3         //外层循环控制冒泡次数
 4         //内存循环比较每次的大小,得到每次的最大值(泡)
 5  
 6         for($i = 0,$length = count($arr);$i < $length;$i++){
 7         
 8                  //内存循环
 9                  for($j = 0;$j < ($length - $i - 1);$j++){
10                          //拿着j变量所对应的数组元素,与后面的元素进行比较
11                          if($arr[$j] > $arr[$j + 1]){
12                                   //交换位置
13                                   $temp              = $arr[$j];
14                                   $arr[$j]           = $arr[$j+1];
15                                   $arr[$j+1]         = $temp;
16                          }
17                  }
18         }

总结:

冒泡排序最好的时间复杂度是O(n),虽然说它不是最优的算法,但是这是我们经常接触到的,面试也会给问到,所以我们一定要懂的基本原理,能理解到,能写的出来

 

快速排序:用空间换时间

基本思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

图解:

 

 

找到当前数组中的任意一个元素,作为标准,新建两个空数组,遍历整个数组元素,遍历到的元素比当前元素要小,那么放到左边的数组;如果要大,放到另外一个数组中

递归思路

1.递归点:如果两个数组的元素大于1,就需要再进行分解

2.递归出口:数组元素变成1的时候

代码:

        
 1 //待排序数组
 2         $arr = array(5,3,8,2,6,4,7);
 3         //函数实现快速排序
 4         function quick_sort($arr){
 5                  //判断参数是否是一个数组
 6                  if(!is_array($arr)) return false;
 7  
 8                  //递归出口:数组长度为1就直接返回数组
 9                  $length = count($arr);
10                  if($length <= 1) return $arr;
11 
12                  //数组元素有多个
13                  $left = $right = array();
14                  //使用for循环进行遍历,把第一个元素当做比较的对象
15                  for($i = 1;$i < $length;$i++){
16                          //判断当前元素值的大小
17                          if($arr[$i] < $arr[0]){
18                                   //当前元素小于标准元素,放到左边数组
19                                   $left[] = $arr[$i];
20                          }else{
21                                   $right[] = $arr[$i];
22                          }
23                  }
24                  //递归调用
25                  $left = quick_sort($left);
26                  $right = quick_sort($right);
27  
28                  //将所有的结果合并
29                  return array_merge($left,array($arr[0]),$right);
30         }

总结:

快速排序在一般的排序的方式中最快的排序方式,以递归为基础,使用空间换时间。在一般的面试中会给问到,要能知道基础原理。

 

------------------------------------------------------------------------------

欢迎关注我的公众号【phper的进阶之路】,将不断更新各种技术心得,免费提供各种学习资源!!!
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
算法之常见排序算法-冒泡排序、归并排序、快速排序

对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职之后才知道,这面试...

Linux就该这么学
2019/10/21
12
0
算法之常见排序算法-冒泡排序、归并排序、快速排序

引言 对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职之后才知道,...

osc_w6ku5hr7
04/16
3
0
JavaScript数据结构与算法(排序算法)

比较排序算法一般有三个指标 时间复杂度, 算法执行完成所需要的时间 空间复杂度, 算法执行完成所需要的空间 稳定性,当二个元素的值相同的时候,排序之后二个元素的前后位置是否发生改变 ...

fiveoneLei
2018/07/17
0
0
面试必知的冒泡排序和快速排序

前一篇给大家介绍了《优化的直接插入排序(二分查找插入排序,希尔排序)》,现在继续介绍其他排序算法 本博文介绍两个最常被提起的排序算法:冒泡排序和快速排序。冒泡排序是入门排序算法,...

滴答的雨
2014/07/17
0
0
丰富图例讲解十大经典排序算法 | 面试必备

面试官问:你会三路快排吗? 我: ... 关于时间复杂度: 平方阶 (O(n**2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。 线性对数阶 (O(nlog2n)) 排序: 快速排序、堆排序和归并排序;...

云影sky
2019/09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud开发人员如何解决服务冲突和实例乱窜?(IP实现方案)

点击上方“陶陶技术笔记”关注我 回复“资料”获取作者整理的大量学习资料! 一、背景 在我上一篇文章《Spring Cloud开发人员如何解决服务冲突和实例乱窜?》中提到使用服务的元数据来实现隔...

zlt2000
2019/09/06
0
0
Linux下diff命令用法详解

大家好,我是良许。 我们在平时工作的时候,经常要知道两个文件之间,以及同个文件不同版本之间有何异同点。在 Windows 下,有 beyond compare 这个好用的工具,而在 Linux 下,也有很多很强...

osc_th8jvcw7
59分钟前
7
0
万变不离其宗之UART要点总结

[导读] 单片机开发串口是应用最为广泛的通信接口,也是最为简单的通信接口之一,但是其中的一些要点你是否明了呢?来看看本人对串口的一些总结,当然这个总结并不能面面俱到,只是将个人认为...

osc_kyehmyzk
今天
7
0
kafka的认识、安装与配置

认识Kafka 花费越少的精力在数据移动上,就能越专注于核心业务 --- 《Kafka:The Definitive Guide》 认识 Kafka 之前,先了解一下发布与订阅消息系统:消息的发送者不会直接把消息发送给接收...

osc_wy8nhxhn
今天
0
0
使用pandas进行数据处理——DataFrame篇

  今天是pandas数据处理专题的第二篇文章,我们一起来聊聊pandas当中最重要的数据结构——DataFrame。   上一篇文章当中我们介绍了Series的用法,也提到了Series相当于一个一维的数组,只...

开源仔
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部