排序算法之快速排序

基本思想

任取待排元素序列中的某个元素（例如第一个元素）作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：左侧子序列中所有元素的排序码都小于基准元素的排序码，右侧子序列中所有元素的排序码都大于或等于基准元素的排序码，基准元素则排在这两个子序列中间（这也是该元素最终安放的位置）。然后分别对这两个子序列重复进行上述方法，直到所有的元素都排在相应的位置上为止。

代码

private void quickSort(int[] a, int left, int right) {
    if (left < right) {
        int pivotpos = partition(a, left, right);
        quickSort(a, left, pivotpos - 1);
        quickSort(a, pivotpos + 1, right);
    }
}

private int partition(int[] a, int low, int high) {
    int temp = a[low];
    while (low < high) {
        while (low < high && temp <= a[high])
            high--;
        a[low] = a[high];
        while (low < high && temp >= a[low])
            low++;
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}

性能分析

快速排序的平均时间复杂度为$O(nlog_2n)$。就平均时间复杂度而言，快速排序是所有内部排序方法中最好的一个。由于快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数，最大递归调用层次与递归树的深度一致，理想情况为$?log_2(n+1)?$。因此，要求存储开销为$O(log_2n)$。但是，我们每次都选用序列的第一个元素作为比较的基准元素。这样的选择简单但并不理想。在最坏的情况下，即待排序元素已经有序的情况下，其递归数成为单支树，每次划分只得到一个比上一次少一个元素的子序列。其排序速度退化到简单排序的水平，比直接插入排序还要慢。占用附加存储（即栈）将达到$O(n)$。另外，基本的快速排序算法，对于n较大的平均情况而言，快速排序是“快速”的，但是当n很小时，这种排序方法往往比其他简单排序方法还要慢。