快速排序
原理
快速排序是C.R.A.Hoare提出的一種交換排序仰剿。它采用分治的策略日川，所以也稱其為分治排序寓盗。
實現(xiàn)快速排序算法的關(guān)鍵在于，先在數(shù)組中選一個數(shù)作為基數(shù)望侈，接著以基數(shù)為中心將數(shù)組中的數(shù)字分為兩部分印蔬，比基數(shù)小的放在數(shù)組的左邊，比基數(shù)大的放到數(shù)組的右邊脱衙。接下來我們可以用遞歸的思想分別對基數(shù)的左右兩邊進行排序侥猬。
整個快速排序可以總結(jié)為以下三步：
- 從數(shù)組中取出一個數(shù)作為基數(shù)
- 分區(qū)，將數(shù)組分為兩部分捐韩，比基數(shù)小的放在數(shù)組的左邊退唠，比基數(shù)大的放到數(shù)組的右邊。
- 遞歸使左右區(qū)間重復(fù)第二步荤胁，直至各個區(qū)間只有一個數(shù)瞧预。
樣例分析
下面我用博客專家MoreWindows的挖坑填數(shù)+分治思想來分析一個實例（使用快速排序?qū)⒁韵聰?shù)組排序）
首先，取數(shù)組中的第一個數(shù)字52為第一次分區(qū)的基數(shù)
初始時，start=0垢油、end=8盆驹、base=52（start區(qū)間的頭、end區(qū)間的尾滩愁、base基數(shù)）
由于將array[0]中的數(shù)據(jù)賦給了基數(shù)base躯喇，我們可以理解為在array[0]處挖了一個坑，當(dāng)然這個坑是可以用其它數(shù)據(jù)來填充的硝枉。
接著我們從end開始 向前找比base小或者等于base的數(shù)據(jù)玖瘸，很快我們就找了19，我們就19這個數(shù)據(jù)填充到array[0]位置檀咙，這樣array[8]位置就又形成了一個新的坑。不怕璃诀，我們接著找符合條件的數(shù)據(jù)來填充這個新坑弧可。
start=0、end=8劣欢、base=52
然后我們再從start開始向后找大于或等于base的數(shù)據(jù)棕诵，找到了88，我們用88來填充array[1]凿将，這樣array[1]位置也形成了一個新坑校套。<span id="inline-blue"> Don't Worry </span>我們接著從end開始 向前找符合條件的數(shù)據(jù)來填充這個坑。
start=1牧抵、end=8笛匙、base=52
{% note success %} 需要注意的是start和end隨著查找的過程是不斷變化的。 {% endnote %}
之后一直重復(fù)上面的步驟犀变，先從前向后找妹孙，再從后向前找。直至所有小于基數(shù)的數(shù)據(jù)都出現(xiàn)在左邊获枝，大于基數(shù)的數(shù)據(jù)都出現(xiàn)在右邊蠢正。
最后將base中的數(shù)據(jù)填充到數(shù)組中即可完成這次分區(qū)的過程。
然后遞歸使左右區(qū)間重復(fù)分區(qū)過程省店，直至各個區(qū)間只有一個數(shù)嚣崭，即可完成整個排序過程。
{% note primary %}
快速排序的核心是以基數(shù)為中心懦傍，將數(shù)組分為兩個區(qū)間雹舀，小于基數(shù)的放到基數(shù)的左邊，大于基數(shù)的放到基數(shù)的右邊粗俱。
在第一次分區(qū)的時候我們以數(shù)組中的第一個數(shù)據(jù)為基數(shù)葱跋，在array[0]處挖了一個坑，這時我們只能從區(qū)間的后面往前找小于基數(shù)的數(shù)據(jù)來填充array[0]這個坑，如果直接從前往后找符合條件的數(shù)據(jù)娱俺，就會造成大于基數(shù)的數(shù)據(jù)留在了數(shù)組的左邊稍味。
所以我們只能通過從后往前找小于基數(shù)的數(shù)據(jù)來填充前面的坑，從前往后找大于基數(shù)的數(shù)據(jù)來填充后面的坑荠卷。這樣可以保證在只遍歷一遍數(shù)組就能將數(shù)組分為兩個區(qū)間
最后一步我們用基數(shù)本身來填充數(shù)組的最后一個坑
{% endnote %}
代碼實現(xiàn)：
// 分區(qū)
public static int partition(int[] array, int start, int end) {
int base = array[start];
while (start < end) {
while (start < end && array[end] >= base)
end --;
array[start] = array[end];
while (start < end && array[start] <= base)
start ++;
array[end] = array[start];
}
array[end] = base;
return start;
}
// 快速排序
public static void quickSort(int[] array,int start, int end) {
if(start < end) {
int index = partition(array, start, end);
quickSort(array, start, index-1);
quickSort(array, index+1, end);
}
}
class QuickSort {
public:
//快速排序
int* quickSort(int* A, int n) {
QSort(A,0,n-1);
return A;
}
//對數(shù)組A[low,...,high]
void QSort(int *A,int low,int high) {
if(low<high) {
int n;
n=Partition(A,low,high);
QSort(A,low,n-1);
QSort(A,n+1,high);
}
}
//交換數(shù)組A[low,...,high]的記錄模庐，支點記錄到位，并返回其所在位置油宜，此時
//在它之前（后）的記錄均不大（械嗉睢）于它
int Partition(int *A,int low,int high) {
int key=A[low];
while(low<high) {
while(low<high&&A[high]>=key)
high--;
A[low]=A[high];
while(low<high&&A[low]<=key)
low++;
A[high]=A[low];
}
A[low]=key;
return low;
}
};
算法分析：
當(dāng)數(shù)據(jù)有序時，以第一個關(guān)鍵字為基準(zhǔn)分為兩個子序列慎冤，前一個子序列為空疼燥，此時執(zhí)行效率最差。時間復(fù)雜度為O(n^2)
而當(dāng)數(shù)據(jù)隨機分布時蚁堤，以第一個關(guān)鍵字為基準(zhǔn)分為兩個子序列醉者，兩個子序列的元素個數(shù)接近相等，此時執(zhí)行效率最好披诗。時間復(fù)雜度為O(nlogn)
所以撬即，數(shù)據(jù)越隨機分布時，快速排序性能越好呈队；數(shù)據(jù)越接近有序剥槐，快速排序性能越差。
快速排序在每次“挖坑”的過程中宪摧，需要 1 個空間存儲基數(shù)粒竖。而快速排序的大概需要 NlogN次的處理，所以占用空間也是 NlogN 個几于。
下面我們在來看幾種改進的快排算法
快速排序中元素切分的方式
快速排序中最重要的步驟就是將小于等于中軸元素的整數(shù)放到中軸元素的左邊温圆，將大于中軸元素的數(shù)據(jù)放到中軸元素的右邊，這里我們把該步驟定義為'切分'孩革。以首元素作為中軸元素岁歉，下面介紹幾種常見的'切分方式'。
兩端掃描膝蜈，一端挖坑锅移，另一端填補
這種方法就是我們上面用到的'挖坑填數(shù)'，在這再做個簡單的總結(jié)饱搏。
這種方法的基本思想是：使用兩個變量i和j非剃，i指向最左邊的元素，j指向最右邊的元素推沸，我們將首元素作為中軸备绽，將首元素復(fù)制到變量pivot中券坞，這時我們可以將首元素i所在的位置看成一個坑，我們從j的位置從右向左掃描肺素，找一個小于等于中軸的元素A[j]恨锚，來填補A[i]這個坑，填補完成后倍靡，拿去填坑的元素所在的位置j又可以看做一個坑猴伶，這時我們在以i的位置從前往后找一個大于中軸的元素來填補A[j]這個新的坑，如此往復(fù)塌西，直到i和j相遇（i == j他挎，此時i和j指向同一個坑）。最后我們將中軸元素放到這個坑中捡需。最后對左半數(shù)組和右半數(shù)組重復(fù)上述操作办桨。
這種方法的代碼實現(xiàn)請參考上面的完整代碼。
從兩端掃描交換
這種方法的基本思想是：使用兩個變量i和j站辉，i指向首元素的元素下一個元素（最左邊的首元素為中軸元素）呢撞，j指向最后一個元素，我們從前往后找庵寞，直到找到一個比中軸元素大的，然后從后往前找薛匪，直到找到一個比中軸元素小的，然后交換這兩個元素，直到這兩個變量交錯（i > j）（注意不是相遇 i == j廊谓，因為相遇的元素還未和中軸元素比較）素标。最后對左半數(shù)組和右半數(shù)組重復(fù)上述操作。
public static void QuickSort1(int[] A, int L, int R){
if(L < R){//遞歸的邊界條件娇跟，當(dāng) L == R時數(shù)組的元素個數(shù)為1個
int pivot = A[L];//最左邊的元素作為中軸岩齿，L表示left, R表示right
int i = L+1, j = R;
//當(dāng)i == j時，i和j同時指向的元素還沒有與中軸元素判斷苞俘，
//小于等于中軸元素盹沈，i++,大于中軸元素j--,
//當(dāng)循環(huán)結(jié)束時，一定有i = j+1, 且i指向的元素大于中軸吃谣，j指向的元素小于等于中軸
while(i <= j){
while(i <= j && A[i] <= pivot){
i++;
}
while(i <= j && A[j] > pivot){
j--;
}
//當(dāng) i > j 時整個切分過程就應(yīng)該停止了乞封，不能進行交換操作
//這個可以改成 i < j， 這里 i 永遠不會等于j岗憋， 因為有上述兩個循環(huán)的作用
if(i <= j){
Swap(A, i, j);
i++;
j--;
}
}
//當(dāng)循環(huán)結(jié)束時肃晚，j指向的元素是最后一個（從左邊算起）小于等于中軸的元素
Swap(A, L, j);//將中軸元素和j所指的元素互換
QuickSort1(A, L, j-1);//遞歸左半部分
QuickSort1(A, j+1, R);//遞歸右半部分
}
}
從一端掃描
和前面兩種方法一樣，我們選取最左邊的元素作為中軸元素仔戈，A[1,i]表示小于等于pivot的部分关串，i指向中軸元素（i < 1）拧廊，表示小于等于pivot的元素個數(shù)為0，j以后的都是未知元素（即不知道比pivot大晋修，還是比中軸元素邪赡搿），j初始化指向第一個未知元素飞蚓。
當(dāng)A[j]大于pivot時滤港，j繼續(xù)向前，此時大于pivot的部分就增加一個元素
當(dāng)A[j]小于等于pivot時趴拧，我們注意i的位置溅漾，i的下一個就是大于pivot的元素，我們將i增加1然后交換A[i]和A[j]著榴，交換后小于等于pivot的部分增加1添履，j增加1，繼續(xù)掃描下一個脑又。而i的下一個元素仍然大于pivot暮胧，又回到了先前的狀態(tài)。
public static void QuickSort3(int[] A, int L, int R){
if(L < R){
int pivot = A[L];//最左邊的元素作為中軸元素
//初始化時小于等于pivot的部分问麸，元素個數(shù)為0
//大于pivot的部分往衷，元素個數(shù)也為0
int i = L, j = L+1;
while(j <= R){
if(A[j] <= pivot){
i++;
Swap(A, i, j);
j++;//j繼續(xù)向前，掃描下一個
}else{
j++;//大于pivot的元素增加一個
}
}
//A[i]及A[i]以前的都小于等于pivot
//循環(huán)結(jié)束后A[i+1]及它以后的都大于pivot
//所以交換A[L]和A[i],這樣我們就將中軸元素放到了適當(dāng)?shù)奈恢? Swap(A, L, i);
QuickSort3(A, L, i-1);
QuickSort3(A, i+1, R);
}
}
快速排序的改進方法
三向切分的快速排序
三向切分快速排序的基本思想严卖，用i席舍，j，k三個將數(shù)組切分成四部分哮笆，a[0, i-1]表示小于pivot的部分来颤，a[i, k-1]表示等于pivot的部分，a[j+1]之后的表示大于pivot的部分稠肘，而a[k, j]表示未進行比較的元素（即不知道比pivot大福铅，還是比pivot元素小）项阴。我們要注意a[i]始終位于等于pivot部分的第一個元素滑黔，a[i]的左邊是小于pivot的部分。
我們依舊選取最左邊的元素作為中軸元素环揽，初始化時拷沸，i = L，k = L+1薯演，j=R（L表示最左邊元素的索引撞芍，R表示最右邊元素的索引）
通過上一段的表述可知，初始化時<pivot部分的元素個數(shù)為0跨扮，等于pivot部分元素的個數(shù)為1序无，大于pivot部分的元素個數(shù)為0验毡，這顯然符合目前我們對所掌握的情況。k自左向右掃描直到k與j錯過為止（k > j）帝嗡。
這里我們掃描的目的就是為了逐個減少未知元素晶通，并將每個元素按照和pivot的大小關(guān)系放到不同的區(qū)間上去。
在k的掃描過程中我們可以對a[k]分為三種情況討論
a[k] < pivot 交換a[i]和a[k]哟玷，然后i和k都自增1狮辽，k繼續(xù)掃描
a[k] = pivot k自增1，k接著繼續(xù)掃描
-
a[k] > pivot 這個時候顯然a[k]應(yīng)該放到最右端巢寡，大于pivot的部分喉脖。但是我們不能直接將a[k]與a[j]交換，因為目前a[j]和pivot的關(guān)系未知抑月，所以我們這個時候應(yīng)該從j的位置自右向左掃描树叽。而a[j]與pivot的關(guān)系可以繼續(xù)分為三種情況討論
- a[j] > pivot --- j自減1，j接著繼續(xù)掃描
- a[j] = pivot --- 交換a[k]和a[j]谦絮，k自增1题诵，j自減1，k繼續(xù)掃描（注意此時j的掃描就結(jié)束了）
- a[j] < pivot --- 此時我們注意到a[j] < pivot, a[k] > pivot, a[i] == pivot层皱，那么我們只需要將a[j]放到a[i]上性锭，a[k]放到a[j]上，而a[i]放到a[k]上叫胖。然后i和k自增1草冈，j自減1，k繼續(xù)掃描（注意此時j的掃描就結(jié)束了）
注意臭家，當(dāng)掃描結(jié)束時疲陕，i和j的表示了=等于pivot部分的起始位置和結(jié)束位置方淤。我們只需要對小于pivot的部分以及大于pivot的部分重復(fù)上述操作即可钉赁。
public static void QuickSort3Way(int[] A, int L, int R){
if(L >= R){//遞歸終止條件，少于等于一個元素的數(shù)組已有序
return;
}
int i,j,k,pivot;
pivot = A[L]; //首元素作為中軸
i = L;
k = L+1;
j = R;
OUT_LOOP:
while(k <= j){
if(A[k] < pivot){
Swap(A, i, k);
i++;
k++;
}else
if(A[k] == pivot){
k++;
}else{// 遇到A[k]>pivot的情況携茂，j從右向左掃描
while(A[j] > pivot){//A[j]>pivot的情況,j繼續(xù)向左掃描
j--;
if(j < k){
break OUT_LOOP;
}
}
if(A[j] == pivot){//A[j]==pivot的情況
Swap(A, k, j);
k++;
j--;
}else{//A[j]<pivot的情況
Swap(A, i, j);
Swap(A, j, k);
i++;
k++;
j--;
}
}
}
//A[i, j] 等于 pivot 且位置固定你踩，不需要參與排序
QuickSort3Way(A, L, i-1); // 對小于pivot的部分進行遞歸
QuickSort3Way(A, j+1, R); // 對大于pivot的部分進行遞歸
}
雙軸快速排序
雙軸快速排序算法的思路和上面的三向切分快速排序算法的思路基本一致，雙軸快速排序算法使用兩個軸元素讳苦，通常選取最左邊的元素作為pivot1和最右邊的元素作pivot2带膜。首先要比較這兩個軸的大小，如果pivot1 > pivot2鸳谜，則交換最左邊的元素和最右邊的元素膝藕，已保證pivot1 <= pivot2。雙軸快速排序同樣使用i咐扭，j芭挽，k三個變量將數(shù)組分成四部分
A[L+1, i]是小于pivot1的部分滑废，A[i+1, k-1]是大于等于pivot1且小于等于pivot2的部分，A[j, R]是大于pivot2的部分袜爪，而A[k, j-1]是未知部分蠕趁。和三向切分的快速排序算法一樣，初始化i = L辛馆，k = L+1俺陋，j=R，k自左向右掃描直到k與j相交為止（k == j）昙篙。我們掃描的目的就是逐個減少未知元素腊状，并將每個元素按照和pivot1和pivot2的大小關(guān)系放到不同的區(qū)間上去。
在k的掃描過程中我們可以對a[k]分為三種情況討論（注意我們始終保持最左邊和最右邊的元素瓢对，即雙軸寿酌，不發(fā)生交換）
a[k] < pivot1 i先自增，交換a[i]和a[k]硕蛹，k自增1醇疼，k接著繼續(xù)掃描
a[k] >= pivot1 && a[k] <= pivot2 k自增1，k接著繼續(xù)掃描
-
a[k] > pivot2: 這個時候顯然a[k]應(yīng)該放到最右端大于pivot2的部分法焰。但此時秧荆，我們不能直接將a[k]與j的下一個位置a[--j]交換（可以認為A[j]與pivot1和pivot2的大小關(guān)系在上一次j自右向左的掃描過程中就已經(jīng)確定了，這樣做主要是j首次掃描時避免pivot2參與其中）埃仪，因為目前a[--j]和pivot1以及pivot2的關(guān)系未知乙濒，所以我們這個時候應(yīng)該從j的下一個位置（--j）自右向左掃描。而a[--j]與pivot1和pivot2的關(guān)系可以繼續(xù)分為三種情況討論
- a[--j] > pivot2 j接著繼續(xù)掃描
- a[--j] >= pivot1且a[j] <= pivot2 交換a[k]和a[j]卵蛉，k自增1颁股，k繼續(xù)掃描（注意此時j的掃描就結(jié)束了）
- a[--j] < pivot1 先將i自增1，此時我們注意到a[j] < pivot1, a[k] > pivot2, pivot1 <= a[i] <=pivot2傻丝，那么我們只需要將a[j]放到a[i]上甘有，a[k]放到a[j]上，而a[i]放到a[k]上葡缰。k自增1亏掀，然后k繼續(xù)掃描（此時j的掃描就結(jié)束了）
注意
- pivot1和pivot2在始終不參與k，j掃描過程泛释。
- 掃描結(jié)束時滤愕，A[i]表示了小于pivot1部分的最后一個元素，A[j]表示了大于pivot2的第一個元素怜校，這時我們只需要交換pivot1（即A[L]）和A[i]间影，交換pivot2（即A[R]）與A[j]，同時我們可以確定A[i]和A[j]所在的位置在后續(xù)的排序過程中不會發(fā)生變化（這一步非常重要茄茁，否則可能引起無限遞歸導(dǎo)致的棧溢出）魂贬，最后我們只需要對A[L, i-1]蔓搞，A[i+1, j-1]，A[j+1, R]這三個部分繼續(xù)遞歸上述操作即可随橘。
public static void QuickSortDualPivot(int[] A, int L, int R){
if(L >= R){
return;
}
if(A[L] > A[R]){
Swap(A, L, R); //保證pivot1 <= pivot2
}
int pivot1 = A[L];
int pivot2 = A[R];
//如果這樣初始化 i = L+1, k = L+1, j = R-1,也可以
//但代碼中邊界條件, i,j先增減喂分，循環(huán)截止條件，遞歸區(qū)間的邊界都要發(fā)生相應(yīng)的改變
int i = L;
int k = L+1;
int j = R;
OUT_LOOP:
while(k < j){
if(A[k] < pivot1){
i++;//i先增加机蔗，首次運行pivot1就不會發(fā)生改變
Swap(A, i, k);
k++;
}else
if(A[k] >= pivot1 && A[k] <= pivot2){
k++;
}else{
while(A[--j] > pivot2){//j先增減蒲祈，首次運行pivot2就不會發(fā)生改變
if(j <= k){//當(dāng)k和j相遇
break OUT_LOOP;
}
}
if(A[j] >= pivot1 && A[j] <= pivot2){
Swap(A, k, j);
k++;
}else{
i++;
Swap(A, j, k);
Swap(A, i, k);
k++;
}
}
}
Swap(A, L, i);//將pivot1交換到適當(dāng)位置
Swap(A, R, j);//將pivot2交換到適當(dāng)位置
//一次雙軸切分至少確定兩個元素的位置，這兩個元素將整個數(shù)組區(qū)間分成三份
QuickSortDualPivot(A, L, i-1);
QuickSortDualPivot(A, i+1, j-1);
QuickSortDualPivot(A, j+1, R);
}
下面代碼初始化方式使得邊界條件更加容易確定萝嘁，在下面代碼的方式中A[L+1]A[i-1]表示小于pivot1的部分梆掸，A[i]A[j]表示兩軸之間的部分，A[j]~A[R-1]表示大于pivot2的部分牙言。
當(dāng)排序數(shù)組中不存在pivot1~pivot2中的部分時酸钦，一趟交換完成后i恰好比j大1；當(dāng)排序數(shù)組中僅僅存在一個元素x使得pivot1 <=x <=pivot2時咱枉，一趟交換完成卑硫，i和j恰好相等。
public static void QuickSortDualPivot(int[] A, int L, int R){
if(L >= R){
return;
}
if(A[L] > A[R]){
Swap(A, L, R); //保證pivot1 <= pivot2
}
int pivot1 = A[L];
int pivot2 = A[R];
int i = L+1;
int k = L+1;
int j = R-1;
OUT_LOOP:
while(k <= j){
if(A[k] < pivot1){
Swap(A, i, k);
k++;
i++;
}else
if(A[k] >= pivot1 && A[k] <= pivot2){
k++;
}else{
while(A[j] > pivot2){
j--;
if(j < k){//當(dāng)k和j錯過
break OUT_LOOP;
}
}
if(A[j] >= pivot1 && A[j] <= pivot2){
Swap(A, k, j);
k++;
j--;
}else{//A[j] < pivot1
Swap(A, j, k);//注意k不動
j--;
}
}
}
i--;
j++;
Swap(A, L, i);//將pivot1交換到適當(dāng)位置
Swap(A, R, j);//將pivot2交換到適當(dāng)位置
//一次雙軸切分至少確定兩個元素的位置蚕断，這兩個元素將整個數(shù)組區(qū)間分成三份
QuickSortDualPivot(A, L, i-1);
QuickSortDualPivot(A, i+1, j-1);
QuickSortDualPivot(A, j+1, R);
}
