引言

快速排序是应用最广泛的排序算法(C++中的sort函数内部就是快排)，优点是实现简单，速度快（时间复杂度NlogN），原地排序（只需要很小的辅助栈），缺点就是写的不好性能就会比较差。

基本思想是分治算法：选择一个元素，将数组分割成左右两个数组，左边的数组都比这个数小，右边的数组都比这个数大，再分别递归的对左右数组进行相同的操作，最后达到排序的目的。

基础版快排

思路

快速排序_pic1.png

假设有如上图所示的数组，选择第一个元素4，用某种办法将其放在正确的位置(左边的元素小于4，右边的元素都大于4)，如下图所示：

快速排序_pic2.png

接下来对左边的数组和右边的数组分别按照这个思路递归。

partition

难点是，如何将这个数字4放在正确的位置，这个将数组分为两个部分的操作叫做切分(partition)。通常选择数组的第一个元素v作为数组的分界点，将第一个元素的索引称为l:

快速排序_pic3.png

从l的右边开始遍历并整理数组，使得前面一部分小于v，后面一部分大于v，

快速排序_pic4.png

并用j记录下大于v和小于v的分界点的索引，i记录当前位置的索引。

快速排序_pic5.png

此时，满足条件 arr[l+1...j] < v arr[j+1...i-1]>v。

接下来分为两种情况（暂时未考虑等于）：

1. e>v

   快速排序_pic6.png

此时e>v，所以可以直接将e放在>v的数组的后面，也就是不用动，下一步就是i++，继续判断新的位置的情况。

2. e<v

   快速排序_pic7.png

这种情况可以将e与>v的数组的第一个元素交换，即将i和j+1位置的元素交换。得到：

快速排序_pic8.png

最终，所有元素都遍历完，此时该把v放在正确的位置：

快速排序_pic9.png

正确的位置就是在<v数组的最后一个位置，也就是索引为j的位置，将l和j位置的元素进行交换就可以得到最终结果：

快速排序_pic10.png

接下来就是对左右数组分别进行同样的操作。

代码

// 对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r){
    T v = arr[l];
    int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
    swap( arr[l] , arr[j]);
    return j;
}

// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){
    if( l >= r )
        return;
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){
    __quickSort(arr, 0, n-1);
}

缺陷及优化

缺陷

对于近乎有序的数组，上面的快速排序思路会很慢。快速排序之所以快的一个原因是：将一个数组分为两个部分，分别排序，最好的情况是每次都平分，最后logN次就能完成排序。但是在近乎有序的数组进行排序时，每次选取第一个元素为标定点，最后的切分是极不合理的。如图：

快速排序_pic11.png

最差的情况下，每次选取最左边的元素为标定点，每次都没有元素比他小：

快速排序_pic12.png

改进

不选择第一个元素为标定点，而是从数组长度范围内随机选择一个索引作为标定点。这样的话，出现上面那种情况的概率很小(虽然说不是不可能)，因为每次都选中最小元素几乎不可能。

template <typename T>
int _partition(T arr[], int l, int r){
    //rand()%(r-l+1)+l 在l和r之间产生一个随机数
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
    swap( arr[l] , arr[j]);
    return j;
}

template <typename T>
void _quickSort(T arr[], int l, int r){
//    if( l >= r )
//        return;
    //小优化：在数组长度比较小的时候，使用插入排序更快。
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    int p = _partition(arr, l, r);
    _quickSort(arr, l, p-1 );
    _quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){
    srand(time(NULL)); //用时间当随机种子
    _quickSort(arr, 0, n-1);
}

双路快排

上面的简单排序在切分时，没有考虑到e==v的时候该怎么办，不同的做法，性能差异其实很大。所以在对有大量重复元素的数组进行排序的时候，上面的算法性能很差。

上面的代码实际编写中，隐含着在e==v时，将e保留在原处不动，如图：

快速排序_pic13.png

不管是将e放在<v的数组还是>v的数组，在有大量重复元素的时候，最后两个数组都是极不平均的。

快速排序_pic14.png

思路

将上面切分的思路修改一下，现在将<v的元素和>v的元素分别放在数组的两端：

快速排序_pic15.png

此时需要两个索引i和j，i从左边开始扫描，j从右边开始反向扫描。先对i进行扫描，如果遇到了<v的元素，就继续扫描直到找到 >=v的元素就停下来。如下图：

快速排序_pic16.png

此时，j开始反向扫描，直到遇到<=v的元素就停下来。如下图：

快速排序_pic17.png

此时可以交换i、j索引位置的元素，

快速排序_pic18.png

快速排序_pic19.png

此时，将=v的元素分配给了两边的数组，不会发生聚集在某一侧的情况。结束条件就是i和j相遇。

代码

template <typename T>
int _partition2(T arr[], int l, int r){
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        while( i <= r && arr[i] < v )
            i ++; //搜索arr[i] >= v
        while( j >= l+1 && arr[j] > v )
            j --; //搜索arr[j] <= v
        if( i > j )
            break;
        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }
    swap( arr[l] , arr[j]);
    return j;
}

template <typename T>
void _quickSort(T arr[], int l, int r){
//    if( l >= r )
//        return;
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    int p = _partition2(arr, l, r);
    _quickSort(arr, l, p-1 );
    _quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){
    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

三路快排

没有最优，只有更优，上面双路快排的思想已经很优秀了，但是在解决大量重复元素的情况下，还有一个更加经典的实现方式，也就是这节的主角——三路快排。

思路

不同于上面的快排思想，三路快排直接考虑将数组分为三个部分: >v,=v和<v。

快速排序_pic20.png

上面将数组分为了三个部分，现在考虑i索引位置的e元素，分三种情况：

1. e==v

   快速排序_pic21.png

此时元素e不用进行任何操作。i++。

2. e<v

   快速排序_pic22.png

快速排序_pic23.png

此时将i和lt+1的元素进行交换，lt++; i++。

3. e>v

   快速排序_pic24.png

快速排序_pic25.png

此时，将i和gt-1的元素交换，i++; gt--。

结束条件：i与gt相遇。

快速排序_pic26.png

快速排序_pic27.png

此时将l和lt位置的元素交换，即可完成切分操作，接下来对<v和>v的部分分别切分。优势：可以看到很多元素放在了中间，下次切分的时候少了很多元素！！！。

代码

template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    swap( arr[l], arr[rand()%(r-l+1)+l ] );
    T v = arr[l];
    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }
    swap( arr[l] , arr[lt] );
    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n){
    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}

衍生问题

问题

用快排思想求数组中的第n大的元素（O(n)复杂度）。

思路

快速排序_pic28.png

在快速排序的过程中，一次切分之后，将某个标定元素放在了合适的位置，此时根据该位置的索引p就可以直到这个元素是数组中排名第p的元素，如果n>p，只需要对后面的元素进行一次切分，如果n<p，则需要对前面的元素进行切分，如果n=p，则说明找到了！

总结

从最简单的快速排序算法开始，可以看到算法的一步一步的优化，重要的不是学习快排这个算法，而是学习这个优化思想和思路。要善于分析各种场景下算法的性能，分析性能差的原因，想出解决办法。

参考

程序猿的内功修炼，学好算法与数据结构