假設(shè)我們現(xiàn)在對(duì)“6 ?1 ?2 7 ?9 ?3 ?4 ?5 10 ?8”這個(gè)10個(gè)數(shù)進(jìn)行排序。首先在這個(gè)序列中隨便找一個(gè)數(shù)作為基準(zhǔn)數(shù)（不要被這個(gè)名詞嚇到了霜医，就是一個(gè)用來(lái)參照的數(shù)媳瞪，待會(huì)你就知道它用來(lái)做啥的了）。為了方便，就讓第一個(gè)數(shù)6作為基準(zhǔn)數(shù)吧苛败。接下來(lái)，需要將這個(gè)序列中所有比基準(zhǔn)數(shù)大的數(shù)放在6的右邊径簿，比基準(zhǔn)數(shù)小的數(shù)放在6的左邊罢屈，類(lèi)似下面這種排列：
3 ?1 ?2 5 ?46?9 7 ?10 ?8
在初始狀態(tài)下，數(shù)字6在序列的第1位篇亭。我們的目標(biāo)是將6挪到序列中間的某個(gè)位置缠捌，假設(shè)這個(gè)位置是k。現(xiàn)在就需要尋找這個(gè)k译蒂，并且以第k位為分界點(diǎn)曼月，左邊的數(shù)都小于等于6，右邊的數(shù)都大于等于6柔昼。想一想哑芹，你有辦法可以做到這點(diǎn)嗎？
排序算法顯神威
方法其實(shí)很簡(jiǎn)單：分別從初始序列“6 ?1 ?2 7 ?9 ?3 ?4 ?5 10 ?8”兩端開(kāi)始“探測(cè)”捕透。先從右往左找一個(gè)小于6的數(shù)聪姿，再?gòu)淖笸艺乙粋€(gè)大于6的數(shù)，然后交換他們乙嘀。這里可以用兩個(gè)變量i和j末购，分別指向序列最左邊和最右邊。我們?yōu)檫@兩個(gè)變量起個(gè)好聽(tīng)的名字“哨兵i”和“哨兵j”虎谢。剛開(kāi)始的時(shí)候讓哨兵i指向序列的最左邊（即i=1）盟榴，指向數(shù)字6。讓哨兵j指向序列的最右邊（即=10）婴噩，指向數(shù)字擎场。
首先哨兵j開(kāi)始出動(dòng)羽德。因?yàn)榇颂幵O(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)，所以需要讓哨兵j先出動(dòng)顶籽，這一點(diǎn)非常重要（請(qǐng)自己想一想為什么）玩般。哨兵j一步一步地向左挪動(dòng)（即j--）银觅，直到找到一個(gè)小于6的數(shù)停下來(lái)礼饱。接下來(lái)哨兵i再一步一步向右挪動(dòng)（即i++），直到找到一個(gè)數(shù)大于6的數(shù)停下來(lái)究驴。最后哨兵j停在了數(shù)字5面前镊绪，哨兵i停在了數(shù)字7面前。
現(xiàn)在交換哨兵i和哨兵j所指向的元素的值洒忧。交換之后的序列如下：
6 ?1 ?2?5?9 3 ?4?7?10 ?8
到此蝴韭，第一次交換結(jié)束。接下來(lái)開(kāi)始哨兵j繼續(xù)向左挪動(dòng)（再友情提醒熙侍，每次必須是哨兵j先出發(fā)）榄鉴。他發(fā)現(xiàn)了4（比基準(zhǔn)數(shù)6要小，滿(mǎn)足要求）之后停了下來(lái)蛉抓。哨兵i也繼續(xù)向右挪動(dòng)的庆尘，他發(fā)現(xiàn)了9（比基準(zhǔn)數(shù)6要大，滿(mǎn)足要求）之后停了下來(lái)巷送。此時(shí)再次進(jìn)行交換驶忌，交換之后的序列如下：
6 ?1 ?2 5?4?3 9??7 10 ?8
第二次交換結(jié)束，“探測(cè)”繼續(xù)笑跛。哨兵j繼續(xù)向左挪動(dòng)付魔，他發(fā)現(xiàn)了3（比基準(zhǔn)數(shù)6要小，滿(mǎn)足要求）之后又停了下來(lái)飞蹂。哨兵i繼續(xù)向右移動(dòng)几苍，糟啦！此時(shí)哨兵i和哨兵j相遇了陈哑，哨兵i和哨兵j都走到3面前妻坝。說(shuō)明此時(shí)“探測(cè)”結(jié)束。我們將基準(zhǔn)數(shù)6和3進(jìn)行交換芥颈。交換之后的序列如下：
3?1 2 ?5 ?4 6?9 7 ?10 ?8
到此第一輪“探測(cè)”真正結(jié)束惠勒。此時(shí)以基準(zhǔn)數(shù)6為分界點(diǎn)，6左邊的數(shù)都小于等于6爬坑，6右邊的數(shù)都大于等于6纠屋。回顧一下剛才的過(guò)程盾计，其實(shí)哨兵j的使命就是要找小于基準(zhǔn)數(shù)的數(shù)售担，而哨兵i的使命就是要找大于基準(zhǔn)數(shù)的數(shù)赁遗，直到i和j碰頭為止。
OK族铆，解釋完畢⊙宜模現(xiàn)在基準(zhǔn)數(shù)6已經(jīng)歸位，它正好處在序列的第6位哥攘。此時(shí)我們已經(jīng)將原來(lái)的序列剖煌，以6為分界點(diǎn)拆分成了兩個(gè)序列，左邊的序列是“3 ?1 2 ?5 ?4”逝淹，右邊的序列是“9 ?7 ?10 ?8”耕姊。接下來(lái)還需要分別處理這兩個(gè)序列。因?yàn)?左邊和右邊的序列目前都還是很混亂的栅葡。不過(guò)不要緊茉兰，我們已經(jīng)掌握了方法，接下來(lái)只要模擬剛才的方法分別處理6左邊和右邊的序列即可。現(xiàn)在先來(lái)處理6左邊的序列現(xiàn)吧。
左邊的序列是“3 ?1 ?2 5 ?4”鼎兽。請(qǐng)將這個(gè)序列以3為基準(zhǔn)數(shù)進(jìn)行調(diào)整，使得3左邊的數(shù)都小于等于3莫鸭，3右邊的數(shù)都大于等于3。好了開(kāi)始動(dòng)筆吧
如果你模擬的沒(méi)有錯(cuò)网棍，調(diào)整完畢之后的序列的順序應(yīng)該是：
2 ?1 3?5 ?4
OK黔龟，現(xiàn)在3已經(jīng)歸位。接下來(lái)需要處理3左邊的序列“2 1”和右邊的序列“5 4”滥玷。對(duì)序列“2 1”以2為基準(zhǔn)數(shù)進(jìn)行調(diào)整氏身，處理完畢之后的序列為“1 2”，到此2已經(jīng)歸位惑畴。序列“1”只有一個(gè)數(shù)蛋欣，也不需要進(jìn)行任何處理。至此我們對(duì)序列“2 1”已全部處理完畢如贷，得到序列是“1 2”陷虎。序列“5 4”的處理也仿照此方法，最后得到的序列如下：
1 ?2 ?3 4 ?5 ?6 9 ?7 ?10 ?8
對(duì)于序列“9 ?7 ?10 ?8”也模擬剛才的過(guò)程杠袱，直到不可拆分出新的子序列為止尚猿。最終將會(huì)得到這樣的序列，如下
1 ?2 ?3 4 ?5 ?6 ?7 ?8 9 ?10
到此楣富，排序完全結(jié)束凿掂。細(xì)心的同學(xué)可能已經(jīng)發(fā)現(xiàn)，快速排序的每一輪處理其實(shí)就是將這一輪的基準(zhǔn)數(shù)歸位，直到所有的數(shù)都?xì)w位為止庄萎，排序就結(jié)束了踪少。下面上個(gè)霸氣的圖來(lái)描述下整個(gè)算法的處理過(guò)程。
????public static void main(String[] args) {
????????int[] arr = new int[] { 1, 2, 4, 5, 7, 4, 5, 3, 9, 0 };
?????//System.out.println(Arrays.toString(arr));
????????quickSort(arr);
????????System.out.println(Arrays.toString(arr));
????}
????private static void quickSort(int[] arr) {
????????if (arr.length > 0) {
????????????quickSort(arr, 0, arr.length - 1);
????????}
????}
????private static void quickSort(int[] arr, int low, int high) {
????????// 1.遞歸算法出口
????????if (low > high) { // 放在key之前糠涛，防止下標(biāo)越界
????????????return;
????????}
????????// 2. 存
????????int i = low;
????????int j = high;
????????// key
????????int key = arr[i];
????????// 3.完成一趟排序
????????while (i < j) {
????????????// 從右往左找到第一個(gè)小于key的數(shù)
????????????while (i < j && arr[j] > key) {
????????????????j--;
????????????}
????????????// 從左往右找第一個(gè)大于key的數(shù)
????????????while (i < j && arr[i] <= key) {
????????????????i++;
????????????}
????????????// 交換
????????????if (i < j) {
????????????????int temp = arr[i];
????????????????arr[i] = arr[j];
????????????????arr[j] = temp;
????????????}
????????}
????????// 當(dāng)i==j時(shí)援奢，調(diào)整key的位置
????????int p = arr[i];
????????arr[i] = arr[low];
????????arr[low] = p;
????????// 對(duì)key左邊的數(shù)快排
????????quickSort(arr, low, i - 1);
????????// 對(duì)key右邊的數(shù)快排
????????quickSort(arr, i + 1, high);
????}
