引言
快速排序是应用最广泛的排序算法(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。
接下来分为两种情况（暂时未考虑等于）：
-
e>v
快速排序_pic6.png
此时e>v，所以可以直接将e放在>v的数组的后面，也就是不用动，下一步就是i++，继续判断新的位置的情况。
-
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元素，分三种情况：
-
e==v
快速排序_pic21.png
此时元素e不用进行任何操作。i++。
-
e<v
快速排序_pic22.png
快速排序_pic23.png
此时将i和lt+1的元素进行交换，lt++; i++。
-
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，则说明找到了！
总结
从最简单的快速排序算法开始，可以看到算法的一步一步的优化，重要的不是学习快排这个算法，而是学习这个优化思想和思路。要善于分析各种场景下算法的性能，分析性能差的原因，想出解决办法。
网友评论