快速排序优化-双路快速排序法 Quick Sort 2 Ways

当用快速排序算法对有大量重复数据的数组进行排序的时，快速排序算法的效率会非常低。

这里我们来做一个测试，用快速快速排序和归并排序，对一个100万大小的有大量重复数据的数组（数组中所有的元素都是0到10的数据）进行排序。测试结果如下：

QuickSort: 1000000 true 31678ms

MergeSort: 1000000 true 134ms

从上面的测试结果可以看出，快速排序的效率比归并排序的效率低特别多。

似乎此时快速排序的算法又退化到了O(n^2)的级别，这是为什么呢，我们来分析一下这个问题。

下面这张图是现在Partition过程中，面对每一个元素"e"要执行的操作，我们是要看元素“e”是大于"v"还是小于"v"，然后将它分别放到不同的位置，这样将整个数组分成两个部分，然后再对每一部分递归下去，进行快速排序。

但是要注意，上面的Partition过程中，我们没有讨论如果“e”等于“v”会怎么样。这里可以回想一下上面实现Partition的代码，代码中是如果"e<v"的话把"e"放到橙色部分中，否则的话把"e"放到紫色部分中。相当于代码中隐藏的是如果"e=v"的话，也会被放到紫色的部分中，相当于紫色的部分包含大于等于"v"的元素。

当然了也可以非常轻松的修改代码中的判断条件，把等于"v"的元素放到橙色部分中，相当于橙色的部分包含小于等于"v"的元素。

这里可以想到，不管是把小于等于"v"的元素放到橙色部分，还是把大于等于"v"的元素放到橙色部分，当我们整个数组中包含有大量重复键值的时候，Partition过程都非常有可能把整个数组分成极度不平衡的两个部分，这是因为对于每个键值来说重复的元素太多了，我们选的键值稍微有一点不平衡的话，两部分的差距就会特别的大。即使"v"选在了一个平衡的位置上，但是由于等于"v"的元素也非常多，一样会导致整个数组被分成了两个极其不平衡的部分。那么在这种情况下我们的快速排序就会退化成O(n^2)级别的算法。

如何解决这个问题呢？这里提出一个解决方案，我们换一个思路来实现Partition的过程。

之前我们将"<v"和">v"两个部分都放在数组的左边，"i"从左到右直至遍历完整个数组。新的思路是我们将"<v"和">v"两个部分放在数组的两端，这样就需要一个新的索引“j”，来记录">v"部分下一个要扫描的元素位置。

比如说我们扫描到下面这个状态，接下来要干什么呢？

首先我们从"i"这个 位置开始向后扫描，当扫描到的元素仍然是小余"v"的话，继续向后扫描，直到碰到一个元素"e"大于等于"v"，"i"索引停止扫描。对于索引"j"也是同样的操作，我们从"j"这个位置开始向前扫描，当扫描到的元素大于"v"的话，继续向前扫描，直到碰到一个元素"e"小余等于"v"，"j"索引停止扫描。得到如下图的状态。

上图中两个绿色的部分，分别合并到橙色和紫色的部分。此时数组处于如下的状态。

这时候"i"和"j"所指的元素，只需要交换一下位置，就可以了。

此时橙色的部分都是小于"v"的元素，紫色部分都是大于"v"的元素。然后"i"索引向后移动到下一个待查看的元素，"j"索引向前移动到下一个待查看的元素。直到"i"和"j"两个索引重合

分析上面的流程，会发现上面这张图是有问题的，黄色的部分其实是"<=v"的，紫色的部分其实是">=v"的。

这种Partition的方式所分成的两部分，和之前最大的区别就是把等于"v"的元素，分散到了左右两部分。如果"i"和"j"两个索引指向的元素都等于"v"的，在上面的逻辑里两个元素仍然要交换位置，这样就不会存在大量等于"v"的元素，集中在橙色部分或者是集中在紫色部分。正因为如此，这样的Partition算法，当面临大量重复键值的情况，也能非常好的将它们近乎平分开来。

代码实现如下：

优化后的测试结果如下：

对一百万条随机的数据进行排序

MergeSort: 1000000 true 196ms

QuickSort: 1000000 true 100ms

QuickSort2: 1000000 true 105ms

 

对一百万条近乎有序的数据进行排序

MergeSort: 1000000 true 49ms

QuickSort: 1000000 true 38ms

QuickSort2: 1000000 true 33ms

 

对一百万条拥有大量重复元素的数据进行排序

MergeSort: 1000000 true 151ms

QuickSort: 1000000 true 31010ms

QuickSort2: 1000000 true 46ms

 

从上面的测试结果可以看出，普通的快速排序法对拥有大量重复数据的数组进行排序时，效率非常低下，时间复杂度近乎是O(n^2)。但是使用双路快速排序实现的话，效率得到了极大的优化，甚至比归并排序的效率还要高很多。

这里我们就想，如果我们选中的标识元素"v"有大量和它相等的元素，这些元素是不是都能不参与下一轮的快速排序呢？答案是可以的，下一遍我们将介绍 三路快速排序法 Quick Sort 3 Ways。