Android-Daily-Interview
Android-Daily-Interview copied to clipboard
Published
20 hours ago •
Moosphan
Moosphan
2019-10-17：什么是快速排序？如何优化？
快速排序是从冒泡排序演变而来的算法，但是其比冒泡排序要高效，所以叫做快速排序，简单理解如下。
我举个简单例子来理解吧：
比如我们即将排序的数组如下：
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个规模较小的问题。这些子问题互相独立且与原问题相同。求解这些子问题，然后将子问题的解合并，从而得到原问题的解。
