搜索
首页JavaJava面试题美团面试:请手写一个快排,被我怼了!

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

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

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

面试官:嗯

菜鸟我:不会

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

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

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

想想自己还是太年轻了,换着是现在就不是这样了。写就写嘛,反正不就是一张纸而已。美团面试:请手写一个快排,被我怼了!

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

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

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

背景

来自百科:

快速排序由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 < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就没有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基准大,right比基准小,进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成,让left和right重合的位置和基准交换,返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

输出结果:

[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一个元素为轴心点;
  • 如果两个不相邻元素交换,可以一次交换消除多个逆序,加快排序进程。

后记

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

以上是美团面试:请手写一个快排,被我怼了!的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:Java后端技术全栈。如有侵权,请联系admin@php.cn删除
面试官:Spring Aop 常见注解和执行顺序面试官:Spring Aop 常见注解和执行顺序Aug 15, 2023 pm 04:32 PM

你肯定知道 Spring , 那说说 Aop 的去全部通知顺序, Spring Boot 或者 Spring Boot 2 对 aop 的执行顺序影响?说说你在 AOP 中遇到的那些坑?

某团面试:如果线上遇到了OOM,你该如何排查?如何解决?哪些方案?某团面试:如果线上遇到了OOM,你该如何排查?如何解决?哪些方案?Aug 23, 2023 pm 02:34 PM

OOM 意味着程序存在着漏洞,可能是代码或者 JVM 参数配置引起的。这篇文章和读者聊聊,Java 进程触发了 OOM 后如何排查。

小白也能与BAT面试官对线:CAS小白也能与BAT面试官对线:CASAug 24, 2023 pm 03:09 PM

Java并发编程系列番外篇C A S(Compare and swap),文章风格依然是图文并茂,通俗易懂,让读者们也能与面试官疯狂对线。

饿了么笔试题,看似简单,难倒一批人饿了么笔试题,看似简单,难倒一批人Aug 24, 2023 pm 03:29 PM

在很多公司的笔试题中,千万别小看,都是有坑的,一不小心自己就掉进去了。遇到这种关于循环的笔试题,建议,自己冷静思考,一步一步来。

5道String面试题,能全答对的人不到10%!(附答案)5道String面试题,能全答对的人不到10%!(附答案)Aug 23, 2023 pm 02:49 PM

​这篇来看看关于 Java String类的 5 道面试题,这五道题,我自己在面试过程中亲身经历过几道题目,本篇就带你了解这些题的答案为什么是这样。

上周,XX保险面试,凉了!!!上周,XX保险面试,凉了!!!Aug 25, 2023 pm 03:44 PM

上周,一位群里的朋友去平安保险面试了,结果有些遗憾,蛮可惜的,但希望你不要气馁,正如你所说的,面试中遇到的问题,基本上都是可以通过背面试题解决的,所以请加油!

美团一面,看看你能否回答上来?美团一面,看看你能否回答上来?Aug 24, 2023 pm 03:51 PM

美团一面,看看你能否回答上来?

建议收藏 100 道 Linux 面试题 附答案建议收藏 100 道 Linux 面试题 附答案Aug 23, 2023 pm 02:37 PM

​本文一共 3万多字,分别从 Linux概述、磁盘、目录、文件、安全、语法级、实战、文件管理命令、文档编辑命令、磁盘管理命令、网络通讯命令、系统管理命令、备份压缩命令等方面拆解 Linux 知识点。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),