算法思想：
樹立一個基準(zhǔn)數(shù)(以此數(shù)作為比較的標(biāo)桿),分別從數(shù)組兩邊進(jìn)行探測查找，右邊的探測結(jié)束條件為找到一個比基準(zhǔn)數(shù)小的數(shù)卦停，左邊的探測結(jié)束條件為找到一個基準(zhǔn)數(shù)大的數(shù)族扰，當(dāng)左右兩邊的探測都結(jié)束后，交換這兩個數(shù)宝穗；重復(fù)以上過程鸽照，直到兩邊探測的索引相遇(一致)螺捐。最后將基準(zhǔn)數(shù)與索引相遇的位置上的數(shù)交換颠悬。廢話不多說矮燎，上圖：
假設(shè)我們對{6,1,2,7,9,3,4,5,10,8}這10個數(shù)進(jìn)行排序。
注：i,j分別為左右兩端的探測赔癌，姑且稱它們?yōu)樯诒猓紫壬诒鴍開始出動。因為此處設(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)灾票，所以需要讓哨兵j先出動峡谊，否則會出現(xiàn)遞歸無法退出的情況。哨兵j一步一步地向左挪動(即j--)刊苍，直到找到一個小于6的數(shù)停下來既们，接下來哨兵i再一步一步向右挪動(即i++)，直到找到一個大于6的數(shù)停下來正什。最后哨兵j停在了數(shù)字5面前啥纸，哨兵i停在了數(shù)字7面前。
交換哨兵i和哨兵j所指向元素的值婴氮，交換后序列如下：
6 1 2 5 9 3 4 7 10 8
到此斯棒，第一次交換結(jié)束。接下來哨兵繼續(xù)向左挪動主经。它發(fā)現(xiàn)了4之后停了下來荣暮。哨兵i也繼續(xù)向右挪動，它發(fā)現(xiàn)9之后停了下來罩驻。此時再次進(jìn)行交換穗酥，再次進(jìn)行交換，交換之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交換結(jié)束，探測繼續(xù)砾跃。哨兵j繼續(xù)向左挪動百揭，它發(fā)現(xiàn)了3之后又停了下來。此時哨兵i和哨兵j相遇了蜓席，哨兵i和哨兵j都走到3面前器一。說明此時探測結(jié)束。我們將基準(zhǔn)數(shù)6和3進(jìn)行交換厨内。交換之后的序列如下祈秕。
3 1 2 5 4 6 9 7 10 8
到此第一輪探測真正結(jié)束，此時以6為分界點(diǎn)雏胃，6左邊的數(shù)都小于等于6请毛，6右邊的數(shù)都大于等于。
此時我們已經(jīng)將原來的序列以6為分界點(diǎn)拆分成了兩個序列瞭亮，左邊序列{3,1,2,5,4},右邊序列{9,7,10,8}方仿，接下來只需要再以上述同樣的方法對這兩個序列分別進(jìn)行排序即可。
快排的java實(shí)現(xiàn)：
public class QuickSortTest {
public void quickSort(int[] arr,int left,int right){
if(left > right)
return;
int i = left;
int j = right;
int temp = arr[left];
while(i!=j){
while(i<j && arr[j]>=temp)
j--;
while(i<j && arr[i]<=temp)
i++;
if(i<j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
}
