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

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

菜鸟我：什么意思？这里写吗？（指着简历）

面试官：嗯

菜鸟我：不会

面试官：好吧，今天面试就到这里

菜鸟我：（心里很火，劳资的简历，想在劳资简历上写代码？）沙雕

面试官：（回头看了一眼，一脸懵逼）

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

美团面试：请手写一个快排，被我怼了其实，快排说简单嘛，估计很多人也手写不出来，说难吗也有很多人你能现场手写几种方式。

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

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

背景来自百科：

快速排序由 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 美团面试：请手写一个快排，被我怼了目前数组顺序为[3，1，2，4，9，6]。

下一步：

先将左边先排好序选择元素 3 作为轴心点检查是否 1 < 3 (轴心点)检查是否 2 < 3 (轴心点)将轴心点 3 和存储指数值 2 进行交换现在轴心点已经在排序过后的位置进行拆分 [2,1] 选择 2 作为轴心点检查是否 1 < 2 (轴心点)左边遍历完成，将轴心点 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 一个元素为轴心点；如果两个不相邻元素交换，可以一次交换消除多个逆序，加快排序进程。后记最后再说说，其实你觉得快速排序在工作中有用吗？工作近十年的我真的没用过，但我知道这个快排的思路。如果面试前不准备，我反正是肯定写不出来的，你呢？

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

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

来源：https://mp.weixin.qq.com/s/Hh_-AIfFrEgtjKlLDuejSw