基本的快速排序流程和代码在之前的博客中已经展示。这里主要说明一些快排的问题以及优化手段。
1.快排是递归处理，所以当集合的数字很多时，我们要注意调用栈的深度。如果调用栈超过了限制，就会造成堆栈的溢出。这个时候我们需要对栈最大深度进行设置，一旦达到了这个深度，不能继续递归，而改为其它的排序方法。
2.在快排的时间复杂度的分析中，我们说到了如果一个序列是完全顺序、逆序或者完全相等时，复杂度为O(n^2)。这种情况其实在实际的场景中还是蛮多的，所以在进行快排之前，我们先对其顺序进行一次检查，花比较小的代价就能搞定，如果真的遇到，那么这一次比较甚至后续的递归都可以结束了。
3.随机选取pivot，而不是每次都固定第一位或者最后一位，这样即便是完全顺序或者完全逆序的情况下，最差情况的出现即便在现实情况中也是不太可能的；也有用三位法的，就是左中右分别取一个元素，比较大小，然后取中间值作为区分点。
这里给出代码，在普通快排的基础上，添加了每次排序前的顺序检查，并且使用了随机位置元素的pivot，此时的处理是这一轮的快排开始之前将array[left]与array[position]交换，再进行右边开始的快排操作。这里以最终从小到大的排序作为目标，给出示例：
import java.util.Arrays; import java.util.Random; public class PreCheckOrderQuickSort { public static void sort(int[] array, int start, int end) { if (array == null || array.length < 2 || start >= end || start < 0) { return; } boolean alwaysAsc = true; boolean alwaysDes = true; boolean equal = true; for (int i = start; i < end; i++) { if (array[i] < array[i + 1]) { alwaysDes = false; equal = false; } else if (array[i] > array[i + 1]) { alwaysAsc = false; equal = false; } } if (equal) { System.out.println("equal = " + equal); return; } if (alwaysAsc) { System.out.println("alwaysAsc = " + alwaysAsc); return; } if (alwaysDes) { System.out.println("alwaysDes = " + alwaysDes); reverseArray(array, start, end); return; } int left = start; int right = end; int position = start + new Random().nextInt(end - start + 1); int pivot = array[position]; swapValue(array, left, position); while (left < right) { while (array[right] >= pivot && left < right) { right--; } if (array[right] < pivot) { array[left] = array[right]; } while (array[left] <= pivot && left < right) { left++; } if (array[left] > pivot) { array[right] = array[left]; } if (left == right) { array[left] = pivot; } } if (start < left - 1) { sort(array, start, left - 1); } if (left + 1 < end) { sort(array, left + 1, end); } } private static void reverseArray(int[] array, int start, int end) { for (int i = 0; i < (end - start) / 2; i++) { array[start + i] ^= array[end - i]; array[end - i] ^= array[start + i]; array[start + i] ^= array[end - i]; } } /** * 选定了随机的pivot后，将该位置的元素与array[left]进行交换 * * @param array * @param left * @param position */ private static void swapValue(int[] array, int left, int position) { array[position] ^= array[left]; array[left] ^= array[position]; array[position] ^= array[left]; } public static void main(String[] args) { int[] range = {1, 3, 4, 5, 6, 7, 8, 12, 13, 22, 31, 323, 423}; // reverseArray(range, 0, range.length - 1); sort(range, 0, range.length - 1); System.out.println("range = " + Arrays.toString(range)); } }
实际上，很多函数库中的排序并不是某一种排序单独支持的，比如C语言glibc库中的qsort()函数。它会优先使用归并排序，尽管归并排序的空间复杂度是O(n)，但对于小规模的数据的排序如1KB-2KB，是可以接受的。但如果数据规模较大，如100M，这时就会改用快速排序，且函数中采用的是三数取中，对于栈深的问题，qsort通过实现了一个栈，模拟递归函数的调用栈来解决。另外，子区间中的元素个数小于4时，函数会选择插入排序对小区间进行排序。在小规模数据面前，O(n^2)的执行效率不见得比O(nlogn)低，因为数据规模较小时，我们还需要考虑常数项的影响。可以看到，一个真正落地的排序函数，是需要考虑实际场景的，不同规模不同场景下是需要结合不同类型的排序组合的。
----------------------------------------------------------------------------------------------------------
大家可以看看自己熟悉的语言提供的函数库中的排序是如何实现的。JDK1.8中，java.util.Arrays中的sort实现里关键是DualPivotQuicksort，双轴快排。
1、N<47 插入排序
2、47<N<286 双轴快排
3、286<N 连续性好 归并排序（Timsort）
4、286<N 连续性不好 双轴快排
其中的双轴快排是对单轴快排的优化，选取排序区间最左侧和最右侧的元素作为两个pivot，即双轴。后续会写blog说明，有兴趣的可以自行查看源码。