盘点那些必问的数据结构算法题之快速排序

0 概述

快速排序也是基于分治模式，类似归并排序那样，不同的是快速排序划分最后不需要merge。对一个数组 A[p..r] 进行快速排序分为三个步骤：

划分：数组 A[p…r] 被划分为两个子数组 A[p…q-1] 和 A[q+1…r]，使得 A[p…q-1] 中每个元素都小于等于 A[q]，而 A[q+1…r] 每个元素都大于 A[q]。划分流程见下图。
解决：通过递归调用快速排序，对子数组分别排序即可。
合并：因为两个子数组都已经排好序了，且已经有大小关系了，不需要做任何操作。

快速排序算法不算复杂的算法，但是实际写代码的时候却是最容易出错的代码，写的不对就容易死循环或者划分错误。

本文代码见

https://github.com/shishujuan/dsalg/tree/master/code/alg/sort

1 朴素的快速排序

这个朴素的快速排序有个缺陷就是在一些极端情况如所有元素都相等时（或者元素本身有序，如 a[] = {1,2,3,4,5}等），朴素的快速算法时间复杂度为 O(N^2)，而如果能够平衡划分数组则时间复杂度为 O(NlgN)。

/**
 * 快速排序-朴素版本
 */
void quickSort(int a[], int l, int u)
{
    if (l >= u) return;

    int q = partition(a, l, u);
    quickSort(a, l, q-1);
    quickSort(a, q+1, u);
}

/**
 * 快速排序-划分函数
 */
int partition(int a[], int l, int u)
{
    int i, q=l;
    for (i = l+1; i <= u; i++) {
        if (a[i] < a[l])
            swapInt(a, i, ++q);
    }
    swapInt(a, l, q);
    return q;
}

2 改进-双向划分的快速排序

一种改进方法就是采用双向划分，使用两个变量 i 和 j，i 从左往右扫描，移过小元素，遇到大元素停止；j 从右往左扫描，移过大元素，遇到小元素停止。然后测试i和j是否交叉，如果交叉则停止，否则交换 i 与 j 对应的元素值。

*注意，如果数组中有相同的元素，则遇到相同的元素时，我们停止扫描，并交换 i 和 j 的元素值。*虽然这样交换次数增加了，但是却将所有元素相同的最坏情况由 O(N^2) 变成了差不多 O(NlgN) 的情况。

比如数组 A={2,2,2,2,2}，则使用朴素快速排序方法，每次都是划分 n 个元素为 1 个和 n-1 个，时间复杂度为 O(N^2)，而使用双向划分后，第一次划分的位置是 2，基本可以平衡划分两部分。

代码如下：

/**
 * 快速排序-双向划分函数
 */
int partitionLR(int a[], int l, int u, int pivot)
{
    int i = l;
    int j = u+1;
    while (1) {
        do {
            i++;
        } while (a[i] < pivot && i <= u); //注意i<=u这个判断条件，不能越界。

        do {
            j--;
        } while (a[j] > pivot);

        if (i > j) break;

        swapInt(a, i, j);
    }

    // 注意这里是交换l和j，而不是l和i，因为i与j交叉后，a[i...u]都大于等于枢纽元t，
    // 而枢纽元又在最左边，所以不能与i交换。只能与j交换。
    swapInt(a, l, j);

    return j;
}

/**
 * 快速排序-双向划分法
 */
void quickSortLR(int a[], int l, int u)
{
    if (l >= u) return;

    int pivot = a[l];
    int q = partitionLR(a, l, u, pivot);
    quickSortLR(a, l, q-1);
    quickSortLR(a, q+1, u);
}

虽然双向划分解决了所有元素相同的问题，但是对于一个已经排好序的数组还是会达到 O(N^2) 的复杂度。此外，双向划分还要注意的一点是代码中循环的写法，如果写成 while(a[i]<t) {i++;} 等形式，则当左右划分的两个值都等于枢纽元时，会导致死循环。

3 继续改进—随机法和三数取中法取枢纽元

为了解决上述问题，可以进一步改进，通过随机选取枢纽元或三数取中方式来获取枢纽元，然后进行双向划分。三数取中指的就是从数组A[l… u]中选择左中右三个值进行排序，并使用中值作为枢纽元。

如数组 A[] = {1, 3, 5, 2, 4}，则我们对 A[0]、A[2]、A[4] 进行排序，选择中值 A4 作为枢纽元，并将其交换到 a[l] ，最后数组变成 A[] = {4 3 5 2 1}，然后跟之前一样双向排序即可。

/**
 * 随机选择枢纽元
 */
int pivotRandom(int a[], int l, int u)
{
    int rand = randInt(l, u);
    swapInt(a, l, rand); // 交换枢纽元到位置l
    return a[l];
}

/**
 * 三数取中选择枢纽元
 */
int pivotMedian3(int a[], int l, int u)
{
     int m = l + (u-l)/2;

     /*
      * 三数排序
      */
     if( a[l] > a[m] )
        swapInt(a, l, m);

     if( a[l] > a[u] )
        swapInt(a, l, u);

     if( a[m] > a[u] )
        swapInt(a, m, u);

     /* assert: a[l] <= a[m] <= a[u] */
     swapInt(a, m, l); // 交换枢纽元到位置l

     return a[l];
}

此外，在数据基本有序的情况下，使用插入排序可以得到很好的性能，而且在排序很小的子数组时，插入排序比快速排序更快，可以在数组比较小时选用插入排序，而大数组才用快速排序。

4 非递归写快速排序

非递归写快速排序着实比较少见，不过练练手总是好的。需要用到栈，注意压栈的顺序。

代码如下：

/**
 * 快速排序-非递归版本
 */
void quickSortIter(int a[], int n)
{
    Stack *stack = stackNew(n);
    int l = 0, u = n-1;
    int p = partition(a, l, u);

    if (p-1 > l) { //左半部分两个边界值入栈
        push(stack, p-1); 
        push(stack, l);
    }

    if (p+1 < u) { //右半部分两个边界值入栈
        push(stack, u);
        push(stack, p+1);
    }

    while (!IS_EMPTY(stack)) { //栈不为空，则循环划分过程
        l = pop(stack);
        u = pop(stack);
        p = partition(a, l, u);

        if (p-1 > l) {
            push(stack, p-1);
            push(stack, l);
        }

        if (p+1 < u) {
            push(stack, u);
            push(stack, p+1);
        }
    }
}

参考资料