快速排序改进优化

本文主要是介绍快速排序改进优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以前写的快速排序，基本上按下面伪代码这个套路写出来就完了，但其实对于快排，可以通过很多方面来进行改进以达到更好的效率。

algorithm quicksort(A, lo, hi) isif lo < hi thenp := partition(A, lo, hi)quicksort(A, lo, p)quicksort(A, p + 1, hi)algorithm partition(A, lo, hi) ispivot := A[lo]i := lo - 1j := hi + 1loop foreverdoi := i + 1while A[i] < pivotdoj := j - 1while A[j] > pivotif i >= j thenreturn jswap A[i] with A[j]

先回顾一下上面快排的模拟图
分析：

• 首先，清楚快排原理的同志都知道，快排特别热衷于凌乱的数据，最好情况下时间复杂度能达到O(nlogn)，空间复杂度为O(logn)；但是对于基本有序或者倒序的数据则无能为力，时间复杂度直接降到O(n^2），空间复杂度为O( n ) 。对于这种情况，取一个合理的基准值就很重要了。
  一种较为稳妥的方法是随机选取数组中的某个位置，而不是总是顽固地选择最右端的元素，这样确实可以避免排序的退化。
  再回想我们为什么要取随机值？就是为了避免输入数据有序造成的异常，如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗？三值取中法就是这样的方法，它的选取方法是先从数组的开头、结尾和中间选取3个元素，再取这3个元素的中间值作为划分的基准。首先，三值取中法本身带有一定的随机性，所以能够很好的处理随机数据；其次，它使得最坏情况几乎不可能发生，如果数组原本就具有有序性，那么按照原始的划分方法，取到的3个元素中必然有2个将被划分到大于（或小于）v的值所在的数组中，而三值取中法则扭转了这种不利；最后，与随机化方法相比，三值取中法省去了生成随机数的开销。
• 其次，在快速排序算法的递归实现中，存在一种不太好的现象：随着递归层层深入，大量数据被分割成了小数组；快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近，比如说对1024进行一次均等划分，那么某个元素可能会移动数百个单位位置，若进行4次均等划分，元素在正确位置上的概率就从1/1024骤升到1/64，考虑到64与1024的绝对数值，这是相当高的效率；然而对于小数组，快速排序的效率就不那么理想了，对于16个元素的数组，快速排序也要划分4次才能把它移动到正确的位置上，相对于之前几百个位置的移动，小数组排序一次只能移动几个单位的位置。
  换句话说，快速排序对少量数据的划分远不如它对大量数据的划分这么划算，当排序进入到小数组阶段后，它将多次因为这些小数组而频繁调用自身，但获得的收益并不大，我姑且把这种现象叫做小数组的边际效益。采取分治递归策略的排序算法（如归并排序）都存在同样的问题，所以这类排序都可以在这方面优化。对大量数据排序时，我们应该在前期利用快速排序的特点，让这些数据迅速移动到正确位置附近，然后在后期消除小数组的边际效应。
  消除边际效应的一个方法就是设定一个M值，当数组元素个数小于M时，视为小数组，此时快速排序就直接返回，最后把数组处理得差不多时，再用其它排序方法对数组进行最终排序。那么M值应该取多少？又应该选择何种排序算法进行最终排序？
  首先回答第二个问题，因为它的答案是显而易见的。对接近有序的数据排序，没有什么算法比插入排序更合适了，插入排序的执行开销与所有元素偏离自己正确位置的距离成正比。

最后看一下结合上面两种改进方法写出来的快排：

package sort;public class QuickSortDemo2 {private static void print(long[] a) {System.out.print("a : ");for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}System.out.println();}private static void quickSort(long[] a, int left, int right) {
//      if(right<=left){
//          return;
//      }//当数组长度比较短并且基本有序时，使用插入排序会有比较好的效率提升if (right - left + 1 <= 10) {insertSort(a, left, right);} else {//取left和right的中间值，有两个好处：1、防止对于基本有序的数组进行多余无效的交换；2、能够很巧妙的为数组越界作参考标准long median = getMedian(a, left, right);int partition = partitionInt(a, left, right, median);quickSort(a, left, partition-1);quickSort(a, partition+1, right);}}private static int partitionInt(long[] a, int left, int right, long median) {int leftPtr = left;int rightPtr = right - 1;while (true) {while (a[++leftPtr] < median)   //因为median取的是left、right和center的中间值，所以仅通过一句判断很巧妙的实现了数组越界的判断;while (a[--rightPtr] > median)  //同上;if(leftPtr >= rightPtr){break;}swap(a,leftPtr,rightPtr);}swap(a, leftPtr, right-1);return leftPtr;}private static long getMedian(long[] a, int left, int right) {int center = (left + right) / 2;if (a[left] > a[center]) {swap(a, left, center);}if (a[left] > a[right]) {swap(a, left, right);}if (a[center] > a[right]) {swap(a, center, right);}swap(a, center, right - 1); //将中值放到right-1位置，后面的比较替换只针对left+1~right-2return a[right - 1];}private static void insertSort(long[] a, int left, int right) {int in, out;for (out = left + 1; out <= right; out++) {in = out;long temp = a[out];while (in > left && a[in - 1] > temp) {a[in] = a[in - 1];--in;}a[in] = temp;}}private static void swap(long[] a, int i, int j) {long temp = a[i];a[i] = a[j];a[j] = temp;}public static void main(String[] args) {long[] a = new long[10000];for (int i = 0; i < a.length; i++) {a[i] = (long) (Math.random() * 99);}print(a);long startTime = System.currentTimeMillis();quickSort(a, 0, a.length - 1);long endTime = System.currentTimeMillis();System.out.println("use: " + (endTime - startTime) + "ms");print(a);}}

github:
https://github.com/aweneves/Algorithm1/blob/master/src/sort/QuickSortDemo2.java

这篇关于快速排序改进优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---