# 每日一问——什么是快速排序？如何优化？

Android每日一问，小聚成河，大聚成江。 更多请访问GitHub Android-Daily-Interview。 注：以下为我个人理解及与大家的回答整理，不定时更新最新回答。

快速排序是从冒泡排序演变而来的算法，但是其比冒泡排序要高效，所以叫做快速排序，简单理解如下。

我举个简单例子来理解吧：

比如我们即将排序的数组如下：

1  8  9  5  6  3  0

我们一般将首位 1 或者最后一个数字 0 认为是基准元素，然后左右对比，大致规律如下：

第一次 ： 将 1 移出，从最右边 数字0 开始，如果 <= 基准数1，则将其移到左边第一个位置，此时 最右边的数字相当于被挖空。

如下，其中 — 代表被挖空的数字

0  8 9 5 6 3 —

接下来从左边开始，如果大于等于基准数1，则将移到右边刚才挖空的位置上，如下：

2 — 9 5 6 3 8

接下来继续从右边开始，刚才右边我们进行到3了，继续左移，如果遇到 <= 基准数 0，那么将其移到刚才 挖的 坑上，如果没有遇到，并且左右操作的数相同时，此时 将 基准数 移动到这个空着的坑位。

如下：

0 1 9 5 6 3 8

我们可以发现，基准数1左边的都小于其，右边的都大于其，所以两边各自继续按照刚才上面的逻辑继续递归。(虽然这里最左边只是0，可以忽略)

接下来的过程如下：

0 1 — 5 6 3 8   (基准数9)

0 1 8 5 6 3 —

0 1 8 5 6 3 9  

0 1 — 5 6 3 9 （基准数8）

0 1 3 5 6 9 _

0 1 3 5 6 _ 9

0 1 3 5 6  8 9  （基准数6）

最后，再盗一张图，详细的看一下

详细参考逻辑，请参考 程序员小灰，后知，后觉

优化：

• 快速排序在序列中元素很少时，效率将比较低，不如插入排序，按需使用。
• 基准数采用随机。
• 尾递归优化。 快速排序和分治排序算法一样，都有两次递归调用，而且快排的递归在尾部，所以我们可以对快排代码实施尾递归优化。减少堆栈深度。
• 将每次分割结束后，将于本次基数相等的元素聚集在一起，再次分割时，避免对聚集过的元素进行分割。
• 多线程优化，基于分治法的思想，将一个规模为 n 的问题分解为 k个规模较小的问题。这些子问题互相独立且与原问题相同。求解这些子问题，然后将子问题的解合并，从而得到原问题的解。

优化参考链接