快速排序[综合优化写法]

优秀快排写法

此文章python写法
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。步骤如下

1. 从数列中挑出一个元素,称为基准(pivot)

2. 分区(partition):遍历数列,比基数小的元素放在左边,比他大的放在右边

   于是此次分区结束后，该基准就处于数列的中间位置，其左边的数全比它小（称为小与子序列），右边的数全比他大（称为大于子序列）。这样一次排序就造成了整体上的有序化。

3. 子数列排序:将小于子数列和大于子序列分别继续快速排序

4. 递归到最底部,数列是零或一,至此,递归结束

针对具体的基数的选择方式和区别方式的不同,主要有四种方式:

• 普通快排
• 随机快排
• 双路快排
• 三路快排

思考:

1.渐进有序的数组和一般乱序的数组,对快排有什么效率的区别

1. 对于快排,就类似于通过分治从顶到底的渐进有序,选择的基数使得分正左右两个子序列长度接近(分区平衡),快排的效率越高.反之使得分区不平衡,快排的效率会降低.

2. 当然当序列有序时,意味着大量元素已经处于有序状态,左边数普遍小于右边,对于普通快排,默认选择左边第一个数作为基准数,这就导致小于基准的数相对于少,而大于基准的数多,造成分区不平衡,严重的话,严重的将退化成O(n^2), 对其改进就是不在使用默认的第一个数,而是选择谁记得一个数位基准,这样的快排称为随机普通快排

3. 实现上，随机普通快排随机选一个数与第一个数交换，然后在将第一个数作为基准（这样代码好写），进行普通快排即可。所以随机普通快排只是对普通快排进行了一下预处理而已。

2.分区时等于的数怎么办？

对于普通快排,我们将等于的数一并放到左边后者右边,在一般情况下,排序效率都很快,能达到O(nlogn),

但是当序列含有大量相等数字时，普通快排会使得大量等于的数集中位于某一边，造成分区不平衡的问题，使得普通快排退化成O(n^2)，

这时对于等于的数的处理就显得很重要了，针对普通快速排序的改进版本——双路排序和三路排序，就应运而生了。

• 双路快排:从两端向中间扫描,等于的数可以被分再任意一边,这样就缓解了分区不平衡问题

• 三路快排：也是从两端向中间扫描，不同的是，它将等于的数通通放到中间，即新增了一个等于区。接下去分别对小与区和大于区继续快排，这样不仅避免了分区不平衡，还有个额外的好处：等于区的数从此不必再处理。

3. 所以双/三路快排一定比普通快排和随机普通快排快吗？

不一定:双路三路快排,只有再序列含有大量相等元素事性能才能比普通的好,负责性能会比普通快排稍差,因为,双/三路快排比普通快排稍复杂,会维护多些指针,就会对对出一些额外的赋值和比较开销

普通快速排序：从左到右或从右到左的单向扫描。设立两个区：小于区，大于等于区

• 问题

  对于渐进有序的数组，效率很差,

  改进选择随机基准,得到随机快速排序

对于含有大量重复元素的序列，即使是随机化快排效率也很差
于是再次改进，

1.双路快排： 从两端向中间挺近，设立两个区：小于等于区，大于等于区
2.三路快排： 从两端向中间挺近，设立三个区：小与区，等于区，大于区

由左到右扫描,设立两个区,小于区,大于等于区

问题1：对于渐进有序的数组，效率不高

原因：快排中分治的不平衡性

我们知道，归并排序复杂度O(nlogn)中logn的原因是每次归并都是高度平衡的，即左右两支长度相等。平衡度越好，性能越接近logn。快排每次都从左边第一个数作为比较数，而对于渐进有序的数组来说，每次区分其实都是极其不平衡的（如下图），甚至会退化成O(n^2).

改进方式：随机化基准数，得到随机普通快排

平均意义上，对于任何数组（包括渐进有序数组），快排遇到最差情况的概率将大大降低。代码如下

问题2：对于含有大量重复元素的数组，即使是改进版的单路快排效率也很差

原因

对于含有大量重复元素的数组，则对于与基准数相同的数，（根据所写代码不同）要么都分到了左边，要么都分到了右边。同样会造成分治不平衡的问题，造成性能退化。如下图所示：

改进算法

1.双路快排： 从两端向中间挺近，设立两个区：小于等于区，大于等于区
2.三路快排： 从两端向中间挺近，设立三个区：小与区，等于区，大于区

从两端向中间挺近，设立两个区：小于等于区，大于等于区

从两端向中间挺近，设立三个区：小与区，等于区，大于区

如何克服含大量重复元素的数组导致不平衡问题：
等于基准的数在正好集中在了中间，而不是任意一边，从而克服了不平衡问题。