美团面试：请手写一个快排，被我怼了！

ゝ一世哀愁。 2022-09-09 12:41 205阅读 0赞

关注公众号“Java后端技术全栈”

回复“000”获取程序员必备电子书

大家好，我是田维常，十年码农给你分享后端开发技术，记得关注我。

我手里有500G后端技术学习资料，文章末尾有我的联系方式，备注“**资源**”。

前面分享8篇，关于2017年，我去上海美团面试遇到的技术问题。

[**美团面试：熟悉哪些JVM调优参数，幸好我准备过！**][JVM]

[美团面试：讲清楚MySQL结构体系，立马发offer][MySQL_offer]

[美团面试：慢SQL有遇到过吗？是怎么解决的？][SQL]

[美团面试：String s = new String("111")会创建几个对象？][String s _ new String_111]

[美团面试：为什么就能直接调用userMapper接口的方法？][userMapper]

[**美团面试：接口被恶意狂刷，怎么办？**][Link 1]

[**美团面试：MySQL中有哪些锁？当时我就懵逼了！**][MySQL]

[**美团面试：使用MySQL，你遇到过哪些坑？**][MySQL 1]

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

> 面试官：我们继续来聊聊关于数据结构与算法，你能写一个快速排序？（说话的同时，把我简历反过来，递给我一支笔，意思就是叫我在自己的简历背后写）
> 
> 菜鸟我：什么意思？这里写吗？（指着简历）
> 
> 面试官：嗯
> 
> 菜鸟我：不会
> 
> 面试官：好吧，今天面试就到这里
> 
> 菜鸟我：（心里很火，劳资的简历，想在劳资简历上写代码？）沙雕
> 
> 面试官：（回头看了一眼，一脸懵逼）

想想自己还是太年轻了，换着是现在就不是这样了。写就写嘛，反正不就是一张纸而已。![8f4c1d23949aafbb333942b75fd6d95c.png][]

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

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

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

## 背景 ##

来自百科：

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

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

可以这么理解：

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

核心思想：

> 先从数列中取出一个数作为基准数，然后进行大小分区；
> 
> 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
> 
> 再对左右区间重复第二步，直到各区间只有一个数，排序完成。

## 实现案例 ##

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

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

第一遍遍历：

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

![6f46da644cecdfee751be1765e97c6b8.gif][]

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

下一步：

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

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

![4f93f3aed2289a099bee38130aaf9466.gif][]

### 2. 快速排序法全流程    ###

![6cc390a304d7149d3d4dc5e6d4162434.gif][]

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

## 后记 ##

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

> 学习算法，收获有两个：思维开发和应付面试。

好了，今天就分享到这里了。期待你的关注、点赞、在看、转发！

加我微信，拉你进群，和大家一起聊技术、谈人生！

![c9d5caa4004e97297e46b39c62175b00.png][]

参考：www.jxbin.com/18007.html

推荐阅读

*  [离职后，10天面试 4 家公司的总结][10_4]  
    
 *  [一套Spring Cloud Alibaba视频教程][Spring Cloud Alibaba]  
    
 *  [后端开发人员，学习之路][Link 2]
 *  [后端面试总结 23万，500多页（含答案）！][23_500]
 *  [112期面试汇总，建议收藏][112]

[JVM]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557df9ca22f4efc57b8abeea251aa4e965c9b08af4428057d8062f8d60032c33f335679d39&idx=1&mid=2247505170&scene=21&sn=36ffb753df777d1b892163e07c22e312#wechat_redirect
[MySQL_offer]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557ab0ca22f3a6754bdd71d976fd22bb3bc65e87f059c9a74f1db3e01f8fdff8d9844ac3e8&idx=1&mid=2247504475&scene=21&sn=11130bc937218b5e052c10cd8fa85a0c#wechat_redirect
[SQL]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557949ca22f05fdf97feeb9f339951bfb62a592823578ae02b557d8f79022e6c02ab85aaab&idx=1&mid=2247504290&scene=21&sn=8431458c6d46bdccc8a91afd95f906de#wechat_redirect
[String s _ new String_111]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd554e7cca22c76a2c897360afa9e0c6f4ed7da42a571673158c2524cf46b2fea901163a474b&idx=1&mid=2247493271&scene=21&sn=f3c5bf9f67971ee6c9dacc0eb757b0e3#wechat_redirect
[userMapper]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd555a1dca22d30b64ae0760054523998b79277c5b6886813011504b7e717a8c29159223596f&idx=1&mid=2247496438&scene=21&sn=02020dac3415ac5d1887b88053d30ffb#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557a94ca22f382326479915ee56139a95ac500a84f057544d8a279be42cfe468c29fd64638&idx=1&mid=2247504511&scene=21&sn=307daa44f37c3d55464e696f0423325d#wechat_redirect
[MySQL]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557b5bca22f24d05c7add694d82f3e3598ed55c4ae4ba8fe133c2dd588da5c841c6f89d313&idx=1&mid=2247504816&scene=21&sn=527ed15852f11904728cb0da164bfa85#wechat_redirect
[MySQL 1]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd557d79ca22f46f643c98c5c4ac55292085a31545580c8f3ba8514aa0138f3391e6979d7ba3&idx=1&mid=2247505298&scene=21&sn=2c3551ca51dabd6943fcc53f66153676#wechat_redirect
[8f4c1d23949aafbb333942b75fd6d95c.png]: /images/20220829/e2e1adf9c9d24a7585e2720afc4632ef.png
[6f46da644cecdfee751be1765e97c6b8.gif]: /images/20220829/3b69af18514d492e98a982f01d8e9aba.png
[4f93f3aed2289a099bee38130aaf9466.gif]: /images/20220829/15479a63351e4c0da0851487c81a089d.png
[6cc390a304d7149d3d4dc5e6d4162434.gif]: /images/20220829/686d6fc9a76842acae972920085f9c72.png
[c9d5caa4004e97297e46b39c62175b00.png]: /images/20220829/8d954b3812114d37b9d441e00111f685.png
[10_4]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd556459ca22ed4faf44bc01dbab47030bae7995cb0bcaa91b55a9e130b2a9e0be119dea29ef&idx=1&mid=2247503026&scene=21&sn=183d38a1172e3eb4d31f60783c477c38#wechat_redirect
[Spring Cloud Alibaba]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd556225ca22eb33a3859702053e4f6817f646264cf58fabe5c9f18144da347305a2a6d8b0e6&idx=2&mid=2247502542&scene=21&sn=efbdc5883e72041b423df9dd229723f1#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd555753ca22de4522b62563737854b0359847f046b416df20cdfa099ea81d8e03c8bb22f4d1&idx=1&mid=2247499704&scene=21&sn=e3a867f360e8a8cccf8d79e0652c36c0#wechat_redirect
[23_500]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd556535ca22ec2350b399f33fd1125ce75dd34f1351b47cb70c2a60ffad803853209fd083b4&idx=1&mid=2247503326&scene=21&sn=a35bd6b6dd62d742f34c7c80e8f8f421#wechat_redirect
[112]: http://mp.weixin.qq.com/s?__biz=MzU4MDM3MDgyMA%3D%3D&chksm=fd556527ca22ec310441fb12453e0bd624fb0e4bfa18919d1141d3641b9c462a9a28113dc95a&idx=2&mid=2247503308&scene=21&sn=0464ed003b29d85ae47f5b330cade32e#wechat_redirect