关于快速排序的相关知识

快速排序主要由四步完成。 1、选择一个数 2、做partition操作 3、分别对左右两个小区间做相同处理 4、直到小区间有序为止 具体过程如下图所示：

代码操作如下

private static void quickSortInternal(long[] array, int lowIndex, int highIndex) { // 由于是闭区间，所以，区间内个个数需要加个 1 int size = highIndex - lowIndex + 1; if (size <= 1) { return; } // 选择其中一个数（选最左边的） —— array[lowIndex] // 执行 partition，小的放左，大的放右 // keyIndex 是经过 partition 之后，选出来的数最终所在下标 int keyIndex = partition(array, lowIndex, highIndex); // 分别对左右区间进行相同的处理 —— 递归方法 quickSortInternal(array, lowIndex, keyIndex - 1); quickSortInternal(array, keyIndex + 1, highIndex); }

其中的partition操作主要有三种方式： 1、Hover法 2、挖坑法 3、左右法

Hover法

private static int partitionHover(long[] array, int lowIndex, int highIndex) { int leftIndex = lowIndex; int rightIndex = highIndex; // 选择的数是最左边的一个 long key = array[lowIndex]; // 选择了最左边，从右边先走 // 停止条件 leftIndex == rightIndex // 循环的继续的条件 leftIndex < rightIndex while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[rightIndex] >= key) { rightIndex--; } // 说明 [rightIndex] 遇到了小的了 while (leftIndex < rightIndex && array[leftIndex] <= key) { leftIndex++; } // 说明 [leftIndex] 遇到了大的了 swap(array, leftIndex, rightIndex); } swap(array, lowIndex, leftIndex); return leftIndex; }

挖坑法

private static int partition挖坑(long[] array, int lowIndex, int hightIndex) { int leftIndex = lowIndex; int rightIndex = hightIndex; long key = array[lowIndex]; while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[rightIndex] >= key) { rightIndex--; } array[leftIndex] = array[rightIndex]; while (leftIndex < rightIndex && array[leftIndex] <= key) { leftIndex++; } array[rightIndex] = array[leftIndex]; } array[leftIndex] = key; return leftIndex; }

左右法

private static int partition前后(long[] array, int lowIndex, int highIndex) { int separateIndex = lowIndex + 1; for (int i = lowIndex + 1; i <= highIndex; i++) { if (array[i] < array[lowIndex]) { swap(array, i, separateIndex); separateIndex++; } } swap(array, lowIndex, separateIndex - 1); return separateIndex - 1; }

关于快速排序的性能 时间复杂度： 最好情况 最坏情况 平均情况 O(n * log(n)) O(n^2) O(n * log(n)) 空间复杂度： 最好情况 最坏情况 平均情况 O(log(n)) O(n) O(log(n))

关于快速排序的优化

1、partition选择挖坑法 2、数量比较少时，不够快（当区间内的个数少于某个阈值时，使用插排法） 3、优化选择特殊数的方式 （1）随机选 （2）挑几个数，选大小为中间值的（三数取中） 4、相同的值特殊处理