面试官：来，这位精神小伙，简简单单写个快速排序吧

点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝 备战2021秋招面试 微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide

面试现场，终于到了紧张刺激的手撕代码环节，你忐忑的心情随着考官的一句话归于平静。 “ 给 你 二 十 分 钟 ， 你 就 写 个 快 排 吧 ” {\color{red}“给你二十分钟，你就写个快排吧”} “给你二十分钟，你就写个快排吧” 你简直不敢相信眼前这个穿着格子衬衫，牛仔裤角有些发白，头发在风中有些凌乱但仍然难掩老程序员气质的面试官竟然问出这么水的问题，你有些诧异的眼神瞥了一下他，他只是推了推镜框，厚厚的镜片埋下的眼睛连正眼都没有看你。你压抑住自己兴奋激动的心情，“老子早写了八百遍了”，但还是装出若有所思的样子，大约过了十分钟，你把代码甩到了他的脸上，不好意思，这是在梦里， 现实中你恭恭敬敬地交出了如下代码，并幻想着面试官向你投来赞许的目光，后生可畏呀：

眼看面试官一愣，门口的保安拿着对讲机已经蠢蠢欲动，另外一只手隐隐约约拿了样东西，像是砖头，但比砖头略大。你迟疑了几秒，“不好意思不好意思，拿错了，应该是这个“，你挠了挠头，抱歉的样子还是一如往常帅气逼人。

void QuickSort_Core(vector &A, int Left, int Right){
    if(Left>=Right) {return;}
    int pivot = A[0]; 
    int i=Left;
    int j=Right-1;
    while(1){
        while(A[++i]  pivot){}   //从右往左扫，碰到小于pivot的值，就记录下来
        if(i A[center]){
        swap(A[Left],A[center]);
    }
    swap(A[center],A[Right-1]);    //取出中间那个并和最右边倒数第二个调换位置，这样只需要考虑Left+1到Right-2之间的排序
    return A[Right-1];  //返回值当作pivot
}

你甚至耍了点小聪明，把数组的前一个和后两个都一起排序好了。但是，到了现在，快排问法的多种多样已经让你始料未及。

“ 不 错 ， 那 你 回 答 一 下 如 果 和 p i v o t 比 较 过 程 中 ， {\color{red}“不错，那你回答一下如果和pivot比较过程中，} “不错，那你回答一下如果和pivot比较过程中， 如 果 出 现 相 等 的 情 况 怎 么 办 呢 ？ 可 以 直 接 跳 过 吗 ” {\color{red}如果出现相等的情况怎么办呢？可以直接跳过吗”} 如果出现相等的情况怎么办呢？可以直接跳过吗”

你认为如果比较的话会有很多多余的操作，所以你回答应该跳过。

” 你 再 想 想 ， 是 这 样 吗 ？ ” {\color{red}”你再想想，是这样吗？”} ”你再想想，是这样吗？”

到这里，你已经明显感觉到压力。

是 这 样 的 ， 不 停 ， 直 接 跳 过 确 实 可 以 避 免 不 必 要 的 比 较 操 作 ， {\color{red}是这样的，不停，直接跳过确实可以避免不必要的比较操作，} 是这样的，不停，直接跳过确实可以避免不必要的比较操作， 但 是 你 想 象 如 果 是 给 一 个 全 为 1 的 数 组 排 序 ， 最 后 你 的 两 个 {\color{red}但是你想象如果是给一个全为1的数组排序，最后你的两个} 但是你想象如果是给一个全为1的数组排序，最后你的两个 指 针 会 相 遇 在 数 组 尾 端 边 缘 ， 也 就 是 p i v o t 在 那 ， 这 就 和 你 {\color{red}指针会相遇在数组尾端边缘，也就是pivot在那，这就和你} 指针会相遇在数组尾端边缘，也就是pivot在那，这就和你 选 定 p i v o t 在 第 一 个 元 素 那 没 区 别 了 ， 还 是 O ( N 2 ) 。 但 是 ， {\color{red}选定pivot在第一个元素那没区别了，还是O(N^2)。但是，} 选定pivot在第一个元素那没区别了，还是O(N2)。但是， 如 果 你 停 下 来 比 较 的 话 ， 虽 然 耗 费 一 点 运 算 时 间 ， {\color{red}如果你停下来比较的话，虽然耗费一点运算时间，} 如果你停下来比较的话，虽然耗费一点运算时间， 但 是 却 能 使 你 从 两 边 扫 过 来 的 指 针 相 遇 在 大 致 中 间 的 位 置 ， {\color{red}但是却能使你从两边扫过来的指针相遇在大致中间的位置，} 但是却能使你从两边扫过来的指针相遇在大致中间的位置， 这 样 又 可 以 分 治 ， 复 杂 度 可 以 又 达 到 O ( N log ⁡ N ) 。 ” {\color{red}这样又可以分治，复杂度可以又达到O(N\log N)。”} 这样又可以分治，复杂度可以又达到O(NlogN)。”

这时候，你觉得面试官的格子衫和牛仔裤是那么迷人，连隐隐可见的头油都显得光彩夺目，发出关爱智障的光。

那 好 ， 接 下 来 最 后 一 个 问 题 吧 ， 你 说 说 快 速 排 序 有 什 么 弊 端 ？ {\color{red}那好，接下来最后一个问题吧，你说说快速排序有什么弊端？} 那好，接下来最后一个问题吧，你说说快速排序有什么弊端？

你收起了你的痴汉脸，赶紧端正了下，答道：

“快速排序的问题可能就在于它是使用递归的，有的时候效率比较低”

什 么 时 候 呢 ？ {\color{red}什么时候呢？} 什么时候呢？

“因为它是要占用大量系统的堆栈，有很多push和pop的操作，如果数据规模不大的话，是不需要递归的，可以直接用简单排序，比如插入排序就可以了。”

说罢，你擦了擦汗，看着快排已经问了将近一个小时，你似乎对快排有了新的理解。

不 错 ， 那 你 能 写 下 完 整 的 代 码 吗 ？ {\color{red}不错，那你能写下完整的代码吗？} 不错，那你能写下完整的代码吗？

？？？说好的最后一个问题呢？？？

为了读者的一个赞 呸， 为了这个offer，拼了。于是，你又花了些时间，以上面的代码为基础，得到了完整版快速排序，这里的threshold就是你设立的阈值，数组低于这个值时，就可以用插入排序了。

#include 
#include 

using namespace std;
void swap(int &A,int &B){
    int temp = B;
    B = A;
    A = temp;
}

int Median3(vector &A, int Left, int Right){
    int center = (Left+Right)/2;
    if(A[Left] > A[center]){        //两两比较，将三个数排序
        swap(A[Left],A[center]);
    }
    if(A[center] > A[Right]){
        swap(A[Right],A[center]);
    }
    if(A[Left] > A[center]){
        swap(A[Left],A[center]);
    }
    swap(A[center],A[Right-1]);    //取出中间那个并和最右边倒数第二个调换位置，这样只需要考虑Left+1到Right-2之间的排序
    return A[Right-1];
}

void QuickSort_Core(vector &A, int Left, int Right){
	if(Right-Left>=threshold){   //满足就快排
		if(Left>=Right) {return;}
	    int pivot = Median3(A, Left, Right); //此时数组的最左边和最右边的值已经确定，不需要再考虑
	    int i=Left;
	    int j=Right-1;
	    while(1){
	        while(A[++i]  pivot){}   //从右往左扫，碰到小于pivot的值，就记录下来
	        if(i