引言
快速排序是應(yīng)用最廣泛的排序算法(C++中的sort函數(shù)內(nèi)部就是快排)，優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，速度快（時(shí)間復(fù)雜度NlogN），原地排序（只需要很小的輔助棧），缺點(diǎn)就是寫的不好性能就會(huì)比較差。
基本思想是分治算法：選擇一個(gè)元素，將數(shù)組分割成左右兩個(gè)數(shù)組，左邊的數(shù)組都比這個(gè)數(shù)小，右邊的數(shù)組都比這個(gè)數(shù)大，再分別遞歸的對(duì)左右數(shù)組進(jìn)行相同的操作，最后達(dá)到排序的目的。
基礎(chǔ)版快排
思路
假設(shè)有如上圖所示的數(shù)組，選擇第一個(gè)元素4，用某種辦法將其放在正確的位置(左邊的元素小于4，右邊的元素都大于4)，如下圖所示：
接下來對(duì)左邊的數(shù)組和右邊的數(shù)組分別按照這個(gè)思路遞歸。
partition
難點(diǎn)是，如何將這個(gè)數(shù)字4放在正確的位置，這個(gè)將數(shù)組分為兩個(gè)部分的操作叫做切分(partition)。通常選擇數(shù)組的第一個(gè)元素v作為數(shù)組的分界點(diǎn)，將第一個(gè)元素的索引稱為l:
從l的右邊開始遍歷并整理數(shù)組，使得前面一部分小于v，后面一部分大于v，
并用j記錄下大于v和小于v的分界點(diǎn)的索引，i記錄當(dāng)前位置的索引。
此時(shí)，滿足條件 arr[l+1...j] < v arr[j+1...i-1]>v。
接下來分為兩種情況（暫時(shí)未考慮等于）：
-
e>v
快速排序_pic6.png
此時(shí)e>v，所以可以直接將e放在>v的數(shù)組的后面，也就是不用動(dòng)，下一步就是i++，繼續(xù)判斷新的位置的情況。
-
e<v
快速排序_pic7.png
這種情況可以將e與>v的數(shù)組的第一個(gè)元素交換，即將i和j+1位置的元素交換。得到：
最終，所有元素都遍歷完，此時(shí)該把v放在正確的位置：
正確的位置就是在<v數(shù)組的最后一個(gè)位置，也就是索引為j的位置，將l和j位置的元素進(jìn)行交換就可以得到最終結(jié)果：
接下來就是對(duì)左右數(shù)組分別進(jìn)行同樣的操作。
代碼
// 對(duì)arr[l...r]部分進(jìn)行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;
}
// 對(duì)arr[l...r]部分進(jìn)行快速排序
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);
}
缺陷及優(yōu)化
缺陷
對(duì)于近乎有序的數(shù)組，上面的快速排序思路會(huì)很慢。快速排序之所以快的一個(gè)原因是：將一個(gè)數(shù)組分為兩個(gè)部分，分別排序，最好的情況是每次都平分，最后logN次就能完成排序。但是在近乎有序的數(shù)組進(jìn)行排序時(shí)，每次選取第一個(gè)元素為標(biāo)定點(diǎn)，最后的切分是極不合理的。如圖：
最差的情況下，每次選取最左邊的元素為標(biāo)定點(diǎn)，每次都沒有元素比他?。?/p>
改進(jìn)
不選擇第一個(gè)元素為標(biāo)定點(diǎn)，而是從數(shù)組長度范圍內(nèi)隨機(jī)選擇一個(gè)索引作為標(biāo)定點(diǎn)。這樣的話，出現(xiàn)上面那種情況的概率很小(雖然說不是不可能)，因?yàn)槊看味歼x中最小元素幾乎不可能。
template <typename T>
int _partition(T arr[], int l, int r){
//rand()%(r-l+1)+l 在l和r之間產(chǎn)生一個(gè)隨機(jī)數(shù)
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;
//小優(yōu)化：在數(shù)組長度比較小的時(shí)候，使用插入排序更快。
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)); //用時(shí)間當(dāng)隨機(jī)種子
_quickSort(arr, 0, n-1);
}
雙路快排
上面的簡(jiǎn)單排序在切分時(shí)，沒有考慮到e==v的時(shí)候該怎么辦，不同的做法，性能差異其實(shí)很大。所以在對(duì)有大量重復(fù)元素的數(shù)組進(jìn)行排序的時(shí)候，上面的算法性能很差。
上面的代碼實(shí)際編寫中，隱含著在e==v時(shí)，將e保留在原處不動(dòng)，如圖：
不管是將e放在<v的數(shù)組還是>v的數(shù)組，在有大量重復(fù)元素的時(shí)候，最后兩個(gè)數(shù)組都是極不平均的。
思路
將上面切分的思路修改一下，現(xiàn)在將<v的元素和>v的元素分別放在數(shù)組的兩端：
此時(shí)需要兩個(gè)索引i和j，i從左邊開始掃描，j從右邊開始反向掃描。先對(duì)i進(jìn)行掃描，如果遇到了<v的元素，就繼續(xù)掃描直到找到 >=v的元素就停下來。如下圖：
此時(shí)，j開始反向掃描，直到遇到<=v的元素就停下來。如下圖：
此時(shí)可以交換i、j索引位置的元素，
此時(shí)，將=v的元素分配給了兩邊的數(shù)組，不會(huì)發(fā)生聚集在某一側(cè)的情況。結(jié)束條件就是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);
}
三路快排
沒有最優(yōu)，只有更優(yōu)，上面雙路快排的思想已經(jīng)很優(yōu)秀了，但是在解決大量重復(fù)元素的情況下，還有一個(gè)更加經(jīng)典的實(shí)現(xiàn)方式，也就是這節(jié)的主角——三路快排。
思路
不同于上面的快排思想，三路快排直接考慮將數(shù)組分為三個(gè)部分: >v,=v和<v。
上面將數(shù)組分為了三個(gè)部分，現(xiàn)在考慮i索引位置的e元素，分三種情況：
-
e==v
快速排序_pic21.png
此時(shí)元素e不用進(jìn)行任何操作。i++。
-
e<v
快速排序_pic22.png
此時(shí)將i和lt+1的元素進(jìn)行交換，lt++; i++。
-
e>v
快速排序_pic24.png
此時(shí)，將i和gt-1的元素交換，i++; gt--。
結(jié)束條件：i與gt相遇。
此時(shí)將l和lt位置的元素交換，即可完成切分操作，接下來對(duì)<v和>v的部分分別切分。優(yōu)勢(shì)：可以看到很多元素放在了中間，下次切分的時(shí)候少了很多元素?。?！。
代碼
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);
}
衍生問題
問題
用快排思想求數(shù)組中的第n大的元素（O(n)復(fù)雜度）。
思路
在快速排序的過程中，一次切分之后，將某個(gè)標(biāo)定元素放在了合適的位置，此時(shí)根據(jù)該位置的索引p就可以直到這個(gè)元素是數(shù)組中排名第p的元素，如果n>p，只需要對(duì)后面的元素進(jìn)行一次切分，如果n<p，則需要對(duì)前面的元素進(jìn)行切分，如果n=p，則說明找到了！
總結(jié)
從最簡(jiǎn)單的快速排序算法開始，可以看到算法的一步一步的優(yōu)化，重要的不是學(xué)習(xí)快排這個(gè)算法，而是學(xué)習(xí)這個(gè)優(yōu)化思想和思路。要善于分析各種場(chǎng)景下算法的性能，分析性能差的原因，想出解決辦法。
