歡迎探討铜涉，如有錯(cuò)誤敬請(qǐng)指正
如需轉(zhuǎn)載，請(qǐng)注明出處http://www.cnblogs.com/nullzx/
1. 單軸快速排序的基本原理
快速排序的基本思想就是從一個(gè)數(shù)組中任意挑選一個(gè)元素（通常來(lái)說(shuō)會(huì)選擇最左邊的元素）作為中軸元素遂唧，將剩下的元素以中軸元素作為比較的標(biāo)準(zhǔn)芙代，將小于等于中軸元素的放到中軸元素的左邊，將大于中軸元素的放到中軸元素的右邊盖彭，然后以當(dāng)前中軸元素的位置為界纹烹，將左半部分子數(shù)組和右半部分子數(shù)組看成兩個(gè)新的數(shù)組页滚，重復(fù)上述操作，直到子數(shù)組的元素個(gè)數(shù)小于等于1（因?yàn)橐粋€(gè)元素的數(shù)組必定是有序的）铺呵。
以下的代碼中會(huì)常常使用交換數(shù)組中兩個(gè)元素值的Swap方法裹驰，其代碼如下
public static void Swap(int[] A, int i, int j){
int tmp;
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
2. 快速排序中元素切分的方式
快速排序中最重要的就是步驟就是將小于等于中軸元素的放到中軸元素的左邊，將大于中軸元素的放到中軸元素的右邊陪蜻，我們暫時(shí)把這個(gè)步驟定義為切分邦马。而剩下的步驟就是進(jìn)行遞歸而已，遞歸的邊界條件為數(shù)組的元素個(gè)數(shù)小于等于1宴卖。以首元素作為中軸滋将，看看常見(jiàn)的切分方式。
2.1 從兩端掃描交換的方式
基本思想症昏，使用兩個(gè)變量i和j随闽，i指向首元素的元素下一個(gè)元素（最左邊的首元素為中軸元素），j指向最后一個(gè)元素肝谭，我們從前往后找掘宪，直到找到一個(gè)比中軸元素大的，然后從后往前找攘烛，直到找到一個(gè)比中軸元素小的魏滚，然后交換這兩個(gè)元素，直到這兩個(gè)變量交錯(cuò)（i > j）（注意不是相遇 i == j坟漱，因?yàn)橄嘤龅脑剡€未和中軸元素比較）鼠次。最后對(duì)左半數(shù)組和右半數(shù)組重復(fù)上述操作。
public static void QuickSort1(int[] A, int L, int R){
if(L < R){//遞歸的邊界條件芋齿，當(dāng) L == R時(shí)數(shù)組的元素個(gè)數(shù)為1個(gè)
int pivot = A[L];//最左邊的元素作為中軸腥寇，L表示left, R表示right
int i = L+1, j = R;
//當(dāng)i == j時(shí)，i和j同時(shí)指向的元素還沒(méi)有與中軸元素判斷觅捆，
//小于等于中軸元素赦役，i++,大于中軸元素j--,
//當(dāng)循環(huán)結(jié)束時(shí)，一定有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 時(shí)整個(gè)切分過(guò)程就應(yīng)該停止了掂摔，不能進(jìn)行交換操作
//這個(gè)可以改成 i < j， 這里 i 永遠(yuǎn)不會(huì)等于j赢赊， 因?yàn)橛猩鲜鰞蓚€(gè)循環(huán)的作用
if(i <= j){
Swap(A, i, j);
i++;
j--;
}
}
//當(dāng)循環(huán)結(jié)束時(shí)乙漓，j指向的元素是最后一個(gè)（從左邊算起）小于等于中軸的元素
Swap(A, L, j);//將中軸元素和j所指的元素互換
QuickSort1(A, L, j-1);//遞歸左半部分
QuickSort1(A, j+1, R);//遞歸右半部分
}
}
2.2 兩端掃描，一端挖坑域携，另一端填補(bǔ)
基本思想簇秒，使用兩個(gè)變量i和j，i指向最左邊的元素秀鞭，j指向最右邊的元素趋观，我們將首元素作為中軸扛禽，將首元素復(fù)制到變量pivot中，這時(shí)我們可以將首元素i所在的位置看成一個(gè)坑皱坛，我們從j的位置從右向左掃描编曼，找一個(gè)小于等于中軸的元素A[j]，來(lái)填補(bǔ)A[i]這個(gè)坑剩辟，填補(bǔ)完成后掐场，拿去填坑的元素所在的位置j又可以看做一個(gè)坑，這時(shí)我們?cè)谝詉的位置從前往后找一個(gè)大于中軸的元素來(lái)填補(bǔ)A[j]這個(gè)新的坑贩猎，如此往復(fù)熊户，直到i和j相遇（i == j，此時(shí)i和j指向同一個(gè)坑）吭服。最后我們將中軸元素放到這個(gè)坑中嚷堡。最后對(duì)左半數(shù)組和右半數(shù)組重復(fù)上述操作。
public static void QuickSort2(int[] A, int L, int R){
if(L < R){
//最左邊的元素作為中軸復(fù)制到pivot艇棕，這時(shí)最左邊的元素可以看做一個(gè)坑
int pivot = A[L];
//注意這里 i = L,而不是 i = L+1, 因?yàn)閕代表坑的位置,當(dāng)前坑的位置位于最左邊
int i = L, j = R;
while(i < j){
//下面面兩個(gè)循環(huán)的位置不能顛倒蝌戒，因?yàn)榈谝淮慰拥奈恢迷谧钭筮? while(i < j && A[j] > pivot){
j--;
}
//填A(yù)[i]這個(gè)坑,填完后A[j]是個(gè)坑
//注意不能是A[i++] = A[j],當(dāng)因i==j時(shí)跳出上面的循環(huán)時(shí)
//坑為i和j共同指向的位置,執(zhí)行A[i++] = A[j],會(huì)導(dǎo)致i比j大1，
//但此時(shí)i并不能表示坑的位置
A[i] = A[j];
while(i < j && A[i] <= pivot){
i++;
}
//填A(yù)[j]這個(gè)坑沼琉，填完后A[i]是個(gè)坑北苟，
//同理不能是A[j--] = A[i]
A[j] = A[i];
}
//循環(huán)結(jié)束后i和j相等，都指向坑的位置打瘪，將中軸填入到這個(gè)位置
A[i] = pivot;
QuickSort2(A, L, i-1);//遞歸左邊的數(shù)組
QuickSort2(A, i+1, R);//遞歸右邊的數(shù)組
}
}
2.3 單端掃描方式
j從左向右掃描友鼻，A[1,i]表示小于等于pivot的部分，A[i+1,j-1]表示大于pivot的部分瑟慈，A[j, R]表示未知元素
初始化時(shí)桃移，選取最左邊的元素作為中軸元素屋匕，A[1,i]表示小于等于pivot的部分葛碧，i指向中軸元素（i < 1），表示小于等于pivot的元素個(gè)數(shù)為0过吻，j以后的都是未知元素（即不知道比pivot大进泼，還是比中軸元素小）纤虽，j初始化指向第一個(gè)未知元素乳绕。
當(dāng)A[j]大于pivot時(shí)，j繼續(xù)向前逼纸，此時(shí)大于pivot的部分就增加一個(gè)元素
上圖中假設(shè)對(duì)A[j]與pivot比較后發(fā)現(xiàn)A[j]大于pivot時(shí)洋措，j的變化
當(dāng)A[j]小于等于pivot時(shí)，我們注意注意i的位置杰刽，i的下一個(gè)就是大于pivot的元素菠发，我們將i增加1然后交換A[i]和A[j]王滤，交換后小于等于pivot的部分增加1，j增加1滓鸠，繼續(xù)掃描下一個(gè)雁乡。而i的下一個(gè)元素仍然大于pivot，又回到了先前的狀態(tài)糜俗。
上圖中假設(shè)對(duì)A[j]與pivot比較后發(fā)現(xiàn)A[j] <= pivot時(shí)踱稍，i，j的變化
public static void QuickSort3(int[] A, int L, int R){
if(L < R){
int pivot = A[L];//最左邊的元素作為中軸元素
//初始化時(shí)小于等于pivot的部分悠抹，元素個(gè)數(shù)為0
//大于pivot的部分珠月，元素個(gè)數(shù)也為0
int i = L, j = L+1;
while(j <= R){
if(A[j] <= pivot){
i++;
Swap(A, i, j);
j++;//j繼續(xù)向前，掃描下一個(gè)
}else{
j++;//大于pivot的元素增加一個(gè)
}
}
//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);
}
}
3. 三向切分的快速排序
三向切分快速排序的基本思想楔敌，用i桥温，j，k三個(gè)將數(shù)組切分成四部分梁丘，a[L, i-1]表示小于pivot的部分侵浸，a[i, k-1]表示等于pivot的部分，a[j+1]表示大于pivot的部分氛谜，而a[k, j]表示未判定的元素（即不知道比pivot大掏觉，還是比中軸元素小）值漫。我們要注意a[i]始終位于等于pivot部分的第一個(gè)元素澳腹，a[i]的左邊是小于pivot的部分。
我們選取最左邊的元素作為中軸元素杨何，初始化時(shí)酱塔，i = L，k = L+1危虱，j=R（L表示最左邊元素的索引羊娃，R表示最右邊元素的索引）
通過(guò)上一段的表述可知，初始化時(shí)<pivot部分的元素個(gè)數(shù)為0埃跷，等于pivot部分元素的個(gè)數(shù)為1蕊玷，大于pivot部分的元素個(gè)數(shù)為0，這顯然符合目前我們對(duì)所掌握的情況弥雹。k自左向右掃描直到k與j錯(cuò)過(guò)為止（k > j）垃帅。我們掃描的目的就是逐個(gè)減少未知元素，并將每個(gè)元素按照和pivot的大小關(guān)系放到不同的區(qū)間上去剪勿。
在k的掃描過(guò)程中我們可以對(duì)a[k]分為三種情況討論
（1）a[k] < pivot 交換a[i]和a[k]贸诚，然后i和k都自增1，k繼續(xù)掃描
（2）a[k] = pivot k自增1，k接著繼續(xù)掃描
（3）a[k] > pivot 這個(gè)時(shí)候顯然a[k]應(yīng)該放到最右端酱固，大于pivot的部分二鳄。但是我們不能直接將a[k]與a[j]交換，因?yàn)槟壳癮[j]和pivot的關(guān)系未知媒怯，所以我們這個(gè)時(shí)候應(yīng)該從j的位置自右向左掃描订讼。而a[j]與pivot的關(guān)系可以繼續(xù)分為三種情況討論
3.1）a[j] > pivot j自減1，j接著繼續(xù)掃描
3.2）a[j] == pivot 交換a[k]和a[j]扇苞，k自增1欺殿，j自減1，k繼續(xù)掃描（注意此時(shí)j的掃描就結(jié)束了）
3.3）a[j] < pivot: 此時(shí)我們注意到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ù)掃描（注意此時(shí)j的掃描就結(jié)束了）
注意崖媚，當(dāng)掃描結(jié)束時(shí)亦歉，i和j的表示了=等于pivot部分的起始位置和結(jié)束位置。我們只需要對(duì)小于pivot的部分以及大于pivot的部分重復(fù)上述操作即可畅哑。
public static void QuickSort3Way(int[] A, int L, int R){
if(L >= R){//遞歸終止條件肴楷，少于等于一個(gè)元素的數(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); // 對(duì)小于pivot的部分進(jìn)行遞歸
QuickSort3Way(A, j+1, R); // 對(duì)大于pivot的部分進(jìn)行遞歸
}
4. 雙軸快速排序
雙軸快速排序算法思路和三向切分快速排序算法的思路基本一致赛蔫，雙軸快速排序算法使用兩個(gè)軸，通常選取最左邊的元素作為pivot1和最右邊的元素作pivot2泥张。首先要比較這兩個(gè)軸的大小呵恢，如果pivot1 > pivot2，則交換最左邊的元素和最右邊的元素媚创，已保證pivot1 <= pivot2渗钉。雙軸快速排序同樣使用i，j筝野，k三個(gè)變量將數(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）盅安。我們掃描的目的就是逐個(gè)減少未知元素唤锉，并將每個(gè)元素按照和pivot1和pivot2的大小關(guān)系放到不同的區(qū)間上去。
在k的掃描過(guò)程中我們可以對(duì)a[k]分為三種情況討論（注意我們始終保持最左邊和最右邊的元素别瞭，即雙軸窿祥，不發(fā)生交換）
（1）a[k] < pivot1 i先自增，交換a[i]和a[k]蝙寨，k自增1晒衩，k接著繼續(xù)掃描
（2）a[k] >= pivot1 && a[k] <= pivot2 k自增1，k接著繼續(xù)掃描
（3）a[k] > pivot2: 這個(gè)時(shí)候顯然a[k]應(yīng)該放到最右端大于pivot2的部分墙歪。但此時(shí)听系，我們不能直接將a[k]與j的下一個(gè)位置a[--j]交換（可以認(rèn)為A[j]與pivot1和pivot2的大小關(guān)系在上一次j自右向左的掃描過(guò)程中就已經(jīng)確定了，這樣做主要是j首次掃描時(shí)避免pivot2參與其中）虹菲，因?yàn)槟壳癮[--j]和pivot1以及pivot2的關(guān)系未知靠胜，所以我們這個(gè)時(shí)候應(yīng)該從j的下一個(gè)位置（--j）自右向左掃描。而a[--j]與pivot1和pivot2的關(guān)系可以繼續(xù)分為三種情況討論
3.1）a[--j] > pivot2 j接著繼續(xù)掃描
3.2）a[--j] >= pivot1且a[j] <= pivot2 交換a[k]和a[j]毕源，k自增1浪漠，k繼續(xù)掃描（注意此時(shí)j的掃描就結(jié)束了）
3.3） a[--j] < pivot1 先將i自增1，此時(shí)我們注意到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ù)掃描（此時(shí)j的掃描就結(jié)束了）
注意
1. pivot1和pivot2在始終不參與k，j掃描過(guò)程俱饿。
2. 掃描結(jié)束時(shí)歌粥，A[i]表示了小于pivot1部分的最后一個(gè)元素，A[j]表示了大于pivot2的第一個(gè)元素拍埠，這時(shí)我們只需要交換pivot1（即A[L]）和A[i]失驶，交換pivot2（即A[R]）與A[j]，同時(shí)我們可以確定A[i]和A[j]所在的位置在后續(xù)的排序過(guò)程中不會(huì)發(fā)生變化（這一步非常重要枣购，否則可能引起無(wú)限遞歸導(dǎo)致的棧溢出）嬉探，最后我們只需要對(duì)A[L, i-1]，A[i+1, j-1]棉圈，A[j+1, R]這三個(gè)部分繼續(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先增加胎围，k掃描中pivot1就不參與其中
Swap(A, i, k);
k++;
}else
if(A[k] 大于等于pivot1 && A[k] 小于等于pivot2){
k++;
}else{
while(A[--j] > pivot2){//j先增減，j首次掃描pivot2就不參與其中
if(j <= k){//當(dāng)i和j相遇
break OUT_LOOP;
}
}
if(A[j] 大于等于pivot1 && A[j] 小于等于pivot2){
Swap(A, k, j);
k++;
}else{
i++;
Swap(A, i, j);
Swap(A, j, k);
k++;
}
}
}
Swap(A, L, i);//將pivot1交換到適當(dāng)位置
Swap(A, R, j);//將pivot2交換到適當(dāng)位置
//一次雙軸切分至少確定兩個(gè)元素的位置，這兩個(gè)元素將整個(gè)數(shù)組區(qū)間分成三份
QuickSortDualPivot(A, L, i-1);
QuickSortDualPivot(A, i+1, j-1);
QuickSortDualPivot(A, j+1, R);
}
