From wiki：
快速排序使用 divide-and-conquer 策略来把一个序列分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
Pivot 例子
代码：
public void quickSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
quickSortHelper(array, 0, array.length - 1);
}
private void quickSortHelper(int[] array, int start, int end) {
if (start >= end) {
return;
}
int midIndex = start + (end - start) / 2;
int pivot = array[midIndex]; // pivot can be any random item in the array. Head is typically easier.
int leftIndex = start;
int rightIndex = end;
while (leftIndex <= rightIndex) {
while (array[leftIndex] < pivot) {
leftIndex++;
}
while (array[rightIndex] > pivot) {
rightIndex--;
}
if (leftIndex <= rightIndex) {
swap(array, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
}
// 循环至此，array[leftIndex] >= pivot, array[rightIndex] <= pivot
// start ~ rightIndex, 所有 items <= pivot
// leftIndex ~ end, 所有 items >= pivot
quickSort(array, start, rightIndex);
quickSort(array, leftIndex, end);
}
时间复杂度:
- Average: O(n log n)
- Best: O(n log n)
Quick Sort 不可能比 O(n log n) 更好了。最好的情况，就是每次二分都是均匀二分，从而接近 log n 次递归。
- Worst: O(n^2)
倒序或者顺序，每次取的pivot都为最大值或最小值。这种情况下，相当于 Selection sort 了
空间复杂度： No extra space。
Not stable.
