美团面试:请手写一个快排,被我怼了!

云辰姑娘_7831

云辰姑娘_7831

2023-08-24

1115人浏览

转载

今天,这个题目是当时面试官叫我现场手写快排,场景如下:

面试官:我们继续来聊聊关于数据结构与算法,你能写一个快速排序?(说话的同时,把我简历反过来,递给我一支笔,意思就是叫我在自己的简历背后写)

菜鸟我:什么意思?这里写吗?(指着简历)

面试官:嗯

菜鸟我:不会

面试官:好吧,今天面试就到这里

菜鸟我:(心里很火,劳资的简历,想在劳资简历上写代码?)沙雕

面试官:(回头看了一眼,一脸懵逼)

想想自己还是太年轻了,换着是现在就不是这样了。写就写嘛,反正不就是一张纸而已。

其实,快排说简单嘛,估计很多人也手写不出来,说难吗也有很多人你能现场手写几种方式。

菜鸟我,当年还是能手写一种,毕竟面试前我刚好刻意的准备过“默写快排”。

下面,我们就来分析分析----快速排序。

背景

来自百科:

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以[递归]进行,以此达到整个数据变成有序序列。

这概念理解起来 还是蛮费劲儿的。

可以这么理解:

快速排序是冒泡排序的改进版,整个过程就在拆拆补补,东拆西补或西拆东补,一边拆一边补,直到所有元素达到有序状态。

核心思想:

先从数列中取出一个数作为基准数,然后进行大小分区;

分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;

再对左右区间重复第二步,直到各区间只有一个数,排序完成。

实现案例

下面先通过图文形式一步一步进行拆解。

拿[4,1,6,2,9,3]这个数组举例。

第一遍遍历:

  • 先进行拆分 [4,1,6,2,9,3] 选择元素 4 作为轴心点
  • 检查是否 1
  • 检查是否 6
  • 检查是否 2
  • 2
  • 检查是否 9
  • 检查是否 3
  • 3
  • 将轴心点4和存储指数3进行交换
  • 此时轴心点4左边全部小于4,右边大于4

目前数组顺序为[3,1,2,4,9,6]。

下一步:

  • 先将左边先排好序
  • 选择元素 3 作为轴心点
  • 检查是否 1
  • 检查是否 2
  • 将轴心点 3和存储指数值 2进行交换
  • 现在轴心点已经在排序过后的位置
  • 进行拆分 [2,1] 选择 2 作为轴心点
  • 检查是否 1
  • 左边遍历完成,将轴心点2和存储指数1 进行交换

右边同理……避免视觉疲劳就不一一描述了,可看下面动态演示图。

 

2. 快速排序法全流程

3.代码实现

下面,我们使用Java语言来实现前面的快排案例:

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤:
    //1.比较startIndex和endIndex,更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex  pivot) {
                right--;
            }
          
            while (left <p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;line-height: 26px;">输出结果:</p><pre class="brush:php;toolbar:false;">[1, 2, 3, 4, 6, 9]

代码实现,建议结合前面的动图,理解起来就更简单了。

快排写法还有几种,感兴趣的可以自行查找一下,另外也可以看看维基百科中,快排是怎么介绍的。

4.复杂度分析

时间复杂度:

最坏情况就是每一次取到的元素就是数组中最小/最大的,这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

这种情况时间复杂度就好计算了,就是冒泡排序的时间复杂度:T[n] = n * (n-1) = n^2 + n;

最好情况下是O(nlog2n),推导过程如下:

(递归算法的时间复杂度公式:T[n] = aT[n/b] + f(n)  )

https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.png

所以平均时间复杂度为O(nlog2n)

空间复杂度:

快速排序使用的空间是O(1)的,也就是个常数级;而真正消耗空间的就是递归调用了,因为每次递归就要保持一些数据:

最优的情况下空间复杂度为:O(log2n);每一次都平分数组的情况

最差的情况下空间复杂度为:O( n );退化为冒泡排序的情况

所以平均空间复杂度为O(log2n)

5. 快速排序法总结

  • 默认取第一个元素为轴心点(轴心点的确认区分了 “快速排序法”和“随机排序法”)两种算法,而随机排序则随机rand一个元素为轴心点;
  • 如果两个不相邻元素交换,可以一次交换消除多个逆序,加快排序进程。

后记

最后再说说,其实你觉得快速排序在工作中有用吗?工作近十年的我真的没用过,但我知道这个快排的思路。如果面试前不准备,我反正是肯定写不出来的,你呢?

相关文章

美团
美团

美团app是一款吃喝玩乐一应俱全的生活服务类软件,汇集团购、美食、酒店、外卖、电影、美发、美甲、KTV等服务于一体,为用户提供非常便利且全面的服务,有需要的小伙伴快来保存下载体验吧!

下载

相关标签:

java面试题

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

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

0

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

0

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

0

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

0

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

0

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

0

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

160

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

120

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习