快速排序（簡(jiǎn)稱(chēng)快排）：在待排序數(shù)組中確定一個(gè)基準(zhǔn)值（pivot）攘宙，一次排序后將所有小于基準(zhǔn)值的數(shù)移動(dòng)至基準(zhǔn)值左側(cè)，大于基準(zhǔn)值的數(shù)據(jù)移動(dòng)至基準(zhǔn)值右側(cè)拐迁，這樣基準(zhǔn)值所在的位置就是最終排序后其應(yīng)在位置蹭劈。根據(jù)分治、遞歸的思想线召，對(duì)左右兩側(cè)數(shù)據(jù)遞歸上面的操作铺韧，直至區(qū)間縮小為1，所有的數(shù)據(jù)就都有序了缓淹。
基準(zhǔn)值的選取方法是很關(guān)鍵的（比如三元選取哈打，隨機(jī)選取等），但是并屬于該篇博客的講解范圍讯壶，所以下面為了解釋方便料仗，基準(zhǔn)值暫定的比較隨意，大家諒解 ~
單路快排
下圖中說(shuō)明了一次排序的詳細(xì)流程：核心思想：基準(zhǔn)值定為最右邊伏蚊，i和j從最左邊開(kāi)始罢维，如果j小于基準(zhǔn)值，則i和j交換位置，并且i++肺孵，j++匀借。否則i保持不動(dòng)，j++平窘。最終當(dāng)j移動(dòng)到基準(zhǔn)值所在位置后吓肋，基準(zhǔn)值與i交換位置。
猜想一：基準(zhǔn)值從最左邊開(kāi)始是否可以均蜜？名詞解釋 -- 穩(wěn)定性：經(jīng)過(guò)某種排序算法之后瑰艘，如果相同值的數(shù)據(jù)是鬼，前后順序沒(méi)有發(fā)生改變，我們就把這種算法叫做穩(wěn)定的排序算法紫新。
得出結(jié)論：基準(zhǔn)值必需是j移動(dòng)的結(jié)尾，因?yàn)樽罱K需要一次基準(zhǔn)值和i的交換位置
代碼實(shí)現(xiàn)：
public static void quickSortSingle(int[] arr, int left, int right) {
if (left > right)
return;
int pivot = arr[right];
int i = 0, j = 0;
while (j < right) {
while (j < right && arr[j] <= pivot) {//如果"哨兵"j小于基準(zhǔn)值芒率，則"哨兵"i與"哨兵"j交換位置
swap(arr, i, j);
i++;
j++;
}
j++;
}
//此時(shí)"哨兵"j移動(dòng)到最右側(cè)囤耳，基準(zhǔn)值與哨兵"i"所在位置的值進(jìn)行交換
swap(arr, i, right);
quickSortSingle(arr, left, i - 1);
quickSortSingle(arr, i + 1, right);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
雙路快排
下面按照上述的規(guī)則列出一組數(shù)據(jù)整個(gè)交換流程：核心思想：基準(zhǔn)值在最左邊，“哨兵”i在最左邊偶芍，“哨兵”j在最右邊充择，從右邊（注意要從右邊開(kāi)始，下面會(huì)有說(shuō)明）先開(kāi)始（j--）匪蟀，如果“哨兵”j所在的數(shù)據(jù)小于基準(zhǔn)值則停止椎麦；“哨兵”i開(kāi)始（i++），如果“哨兵”i所在的數(shù)據(jù)大于基準(zhǔn)值則停止材彪，i與j交換位置观挎；如果i和j相遇，則基準(zhǔn)值與i或j（因?yàn)閮烧攥F(xiàn)在一致）交換位置段化。
得出結(jié)論：因?yàn)槿绻葟挠疫呴_(kāi)始會(huì)停留在比基準(zhǔn)值大的數(shù)上，這時(shí)交換基準(zhǔn)值的位置就會(huì)出現(xiàn)問(wèn)題穗泵，所以開(kāi)始執(zhí)行的方向必需是基準(zhǔn)值的反方向普气。
代碼實(shí)現(xiàn)：
public static void quickSortDual(int[] arr, int left, int right) {
if (left > right)
return;
int pivot = arr[left];//基準(zhǔn)值
int i = left;//左側(cè)"哨兵"
int j = right;//右側(cè)"哨兵"
while (i != j) {//注意：要從基準(zhǔn)值所在側(cè)的另外一側(cè)開(kāi)始
while (arr[j] >= pivot && i < j)//如果右側(cè)出現(xiàn)了比基準(zhǔn)值小的元素，則"哨兵"j停留
j--;
while (arr[i] <= pivot && i < j)//如果左側(cè)出現(xiàn)了比基準(zhǔn)值小的元素佃延，則"哨兵"i停留
i++;
if (i < j) {//如果"哨兵"i與j沒(méi)有相遇則交換其所在位置的數(shù)據(jù)
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//此時(shí)"哨兵"i與j相遇现诀，交換基準(zhǔn)值與該相遇點(diǎn)的數(shù)據(jù)
arr[left] = arr[i];
arr[i] = pivot;
quickSortDual(arr, left, i - 1);//遞歸的處理左側(cè)數(shù)據(jù)
quickSortDual(arr, i + 1, right);//遞歸的處理右側(cè)數(shù)據(jù)
}
三路快排
下面按照上述的規(guī)則列出一組數(shù)據(jù)整個(gè)交換流程（雖然該數(shù)據(jù)的排序過(guò)程并沒(méi)有丟失穩(wěn)定性，但是大家不要認(rèn)為三路快排是個(gè)穩(wěn)定排序算法）：核心思想：基準(zhǔn)值在最左邊，“哨兵”i在基準(zhǔn)值右側(cè)加1的位置履肃，“哨兵”j在最右邊仔沿，從基準(zhǔn)值右側(cè)加1的位置開(kāi)始往后遍歷，如果遍歷到的當(dāng)前值小于基準(zhǔn)值尺棋，則當(dāng)前值與左側(cè)"哨兵"交換位置封锉，左側(cè)"哨兵"進(jìn)一，反之，則當(dāng)前值與右側(cè)"哨兵"交換位置成福，左側(cè)"哨兵"退一碾局。
代碼實(shí)現(xiàn)：
public static void quickSortThreeWay(int[] arr, int left, int right) {
if (left > right)
return;
int pivot = arr[left];//基準(zhǔn)值
int i = left;//左側(cè)"哨兵"
int j = right + 1;//右側(cè)"哨兵"
int index = left + 1;
while (index < j) {
if (arr[index] < pivot) {//如果當(dāng)前值小于基準(zhǔn)值奴艾，則當(dāng)前值與左側(cè)"哨兵"交換位置净当，左側(cè)"哨兵"進(jìn)一
swap(arr, index, i + 1);
i++;
index++;
} else if (arr[index] > pivot) {//如果當(dāng)前值大于基準(zhǔn)值，則當(dāng)前值與右側(cè)"哨兵"交換位置蕴潦，左側(cè)"哨兵"退一
swap(arr, index, j - 1);
j--;
} else {
index++;
}
}
swap(arr, left, i);
quickSortSingle(arr, left, i - 1);
quickSortSingle(arr, j, right);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
