vlambda博客
学习文章列表

快速排序到底是多快？

目录

一、简介

二、算法实现

三、性能分析

四、算法优化

五、总结

参考资料

一、简介

快速排序是一种在实际中最常用的一种排序算法，速度快，效率高，可以说最优秀的一种排序算法。其最差的运行时间是O(n^2)，虽然这个时间看起来很差，但是实际中快速排序表现相当好，因为其平均性能很好，期望的运行时间是O(nlogn)，且隐含的常数因子很小。

其次，快速排序是一种原地排序算法，原地排序算法是指在算法过程中需要使用的额外空间是固定的，相反的，归并排序就不是一种原地算法。

二、算法实现

快速排序和归并排序一样，算法实现上也使用了分治思想。

使用切分元素将数组切分为左右两部分，使得左边数组小于切分元素，右边数组大于等于切分元素，接着对左右数组分别递归地进行这样的操作，最终即可使数组有序。

代码如下：

//javapublic class QuickSort<T extends Comparable<T>> extends Sort<T> {

 @Override public void sort(T[] nums) { sort(nums, 0, nums.length - 1); }

 private void sort(T[] nums, int l, int h) { if (h <= l) return; int j = partition(nums, l, h);//切分 sort(nums, l, j - 1); sort(nums, j + 1, h); }

}

对快速排序来说，切分是一个非常重要的操作：对于数组A以及给定的范围low和high，我们将一个元素v作为切分元素（通常是第一个元素），然后，下标i从左向右遍历这个数组，下标j从右向左遍历这个数组；当i遍历过程中遇到大于等于v的元素，同时j遍历过程中遇到小于v的元素，交换i和j，直到i和j相遇，遍历结束。实际上，就是下标i左边维护了一个小于v的数组，而下标j的右边维护一个大于等于v的数组。最后交换v和j，切分操作完成。

代码如下：

//javaprivate int partition(T[] nums, int l, int h) { int i = l, j = h + 1; T v = nums[l]; while (true) { while (less(nums[++i], v) && i != h) ; while (less(v, nums[--j]) && j != l) ; if (i >= j) break; swap(nums, i, j); } swap(nums, l, j); return j;}

当然，切分不止这一种方式：还是使用下标i和j，下标i的左边维护一个小于v的数组，j用来遍历整个数组，当有比v小的元素则加入到小于v的数组中，直到遍历结束，再交换v和i即可。

代码如下：

//javaprivate int partition(T[] nums, int l, int h) { int i = l, j = l; T v = nums[h]; for(; j < h; j++) { if(less(v, nums[j])) { swap(nums, i, j); i++; } } swap(nums, i, h); return i;}

以上就是快速排序的普通实现。

三、性能分析

在最好情况下，我们希望切分元素每次都能将数组切分成大小基本相同的两部分，运行时间的递归式为：T(n)=2*T(n/2)+O(n)；这样递归的层数为lgn层，而每层递归的比较次数为n，因此运行时间为O(nlgn)。

最坏情况下，切分元素刚好是数组的最大或最小元素，数组被切分成的两部分一部分为空，另一部分只比原数组少了个切分元素，运行时间递归式为：T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n)；这导致递归的层数为n层，而每层递归的比较次数为n，因此运行时间为O(n^2)。

因此在实际使用中，我们可以在排序前先将数组打乱，防止最坏情况的出现。

那么快排的普通性能表现如何呢？

我们假设每次递归被划分的左右数组大小比例为9：1。则运行时间的递归式为T(n)=T(9n/10)+T(n/10)+O(n)，O(n)是指一层递归消耗的时间；我们可以得到递归的层数为log<底数>10/9</底数>n，依然为O(lgn)层，因此运行时间依旧为O(nlgn)，当大小比例为99：1时，同理可以推出运行时间依旧为O(nlgn)。

其原因在于，任何一种常数比例的切分，最终递归层数都为O(lgn)层，因此运行时间为O(nlogn)。

注：递归层数计算如下：

假设层数为x层，每次数组都被切分为9n/10和n/10，当递归了x层后，9n/10部分大小变为1，则停止递归（n/10部分肯定先停止了），可以列出方程为：(9n/10)^x=1；解得层数x=log<底数>10/9</底数>n。

四、算法优化

4.1根据分区大小调整算法

这一方面的改进是针对快速排序算法的弱点进行的。快速排序对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计，因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。由此可以得到的改进就是，当数据集较小时，不必继续递归调用快速排序算法，而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成。Introsort就是这样的一种算法，它开始采用快速排序算法进行排序，当递归达到一定深度时就改为堆排序来处理。这样就克服了快速排序在小规模数据集处理中复杂的中轴选择，也确保了堆排序在最坏情况下O(n log n)的复杂度。

另一种优化改进是当分区的规模达到一定小时，便停止快速排序算法。也即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。数列中有部分元素并没有排到最终的有序序列的位置上，但是这种元素并不多。可以对这种“几乎”完成排序的数列使用插入排序算法进行排序以最终完成整个排序过程。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。

另一种快速排序的改进策略是在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。

4.2三平均分区法

关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：

- 首先，它使得最坏情况发生的几率减小了。

- 其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。

4.3三向切分

对于快速排序算法来说，实际上大量的时间都消耗在了分区上面，因此一个好的分区实现是非常重要的。尤其是当要分区的所有的元素值都相等时，一般的快速排序算法就陷入了最坏的一种情况，也即反复的交换相同的元素并返回最差的中轴值。无论是任何数据集，只要它们中包含了很多相同的元素的话，这都是一个严重的问题，因为许多“底层”的分区都会变得完全一样。

对于这种情况的一种改进办法就是将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所有元素，另一块是大于中轴值的所有元素。

//javapublic class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {

 @Override protected void sort(T[] nums, int l, int h) { if (h <= l) { return; } int lt = l, i = l + 1, gt = h; T v = nums[l]; while (i <= gt) { int cmp = nums[i].compareTo(v); if (cmp < 0) { swap(nums, lt++, i++); } else if (cmp > 0) { swap(nums, i, gt--); } else { i++; } } sort(nums, l, lt - 1); sort(nums, gt + 1, h); }}

五、总结

快速排序是被应用最多、实际表现也最好的排序算法。

首先对于运行时间，经过优化后，快排的运行时间为O(nlgn)，这与堆排序、归并排序相同。要强调一点，在每次递归中，其运行时间O(n)的常数因子很小，因此实际的运行时间很快。

同时，由于是原地算法，不需要额外的线性空间，而归并排序则不然。

此外，要注意的是，快速排序是不稳定的。

（写于2018.8.21）

参考资料

- 《算法》

- 《算法导论》

- 快速排序_百度百科