基本的快速排序流程和代码在之前的博客中已经展示。这里主要说明一些快排的问题以及优化手段。 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 其中的双轴快排是对单轴快排的优化，选取排序区间最左侧和最右侧的元素作为两个pivot，即双轴。后续会写blog说明，有兴趣的可以自行查看源码。