今天,这个题目是当时面试官叫我现场手写快排,场景如下:
面试官:我们继续来聊聊关于数据结构与算法,你能写一个快速排序?(说话的同时,把我简历反过来,递给我一支笔,意思就是叫我在自己的简历背后写)
菜鸟我:什么意思?这里写吗?(指着简历)
面试官:嗯
菜鸟我:不会
面试官:好吧,今天面试就到这里
菜鸟我:(心里很火,劳资的简历,想在劳资简历上写代码?)沙雕
面试官:(回头看了一眼,一脸懵逼)
想想自己还是太年轻了,换着是现在就不是这样了。写就写嘛,反正不就是一张纸而已。
其实,快排说简单嘛,估计很多人也手写不出来,说难吗也有很多人你能现场手写几种方式。
菜鸟我,当年还是能手写一种,毕竟面试前我刚好刻意的准备过“默写快排”。
下面,我们就来分析分析----快速排序。
背景
来自百科:
快速排序由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中文网其他相关文章!

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

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

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

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

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

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

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


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

PhpStorm Mac 版本
最新(2018.2.1 )专业的PHP集成开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

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