O(n log n) - Quick Sort

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.

O(n log n) - Quick Sort

推荐阅读更多精彩内容