舉個例子
排序這個序列：6 1 2 7 9 3 4 5 10 8
- 步驟1：選擇一個基準數(shù)作為對比的開始值昭殉，這里選擇第一個數(shù)6：
- 步驟2、先從右往左找一個小于 6 的數(shù)郁稍，再從左往右找一個大于 6 的數(shù)烙心。
- 步驟3、然后交換他們
變成這樣子：
繼續(xù)執(zhí)行步驟2和3拙已，直到兩個哨兵相遇，：
左右兩個哨兵都走到3：
- 步驟4:將開始選擇基準數(shù)字6換到中間摧冀，測試6左邊的數(shù)都小于6倍踪，右邊的數(shù)都大于6。完成第一次循環(huán):
第一次完成之后索昂，再按照此方法分別對6左右兩邊的數(shù)列進行遞歸排序即可建车。是不是很簡單。
看下代碼就更清晰了：
void quicksort(int a[], int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的就是基準數(shù)
i=left;
j=right;
while(i!=j)
{
//順序很重要椒惨，要先從右邊開始找
while(a[j]>=temp && i<j)
j--;
//再找右邊的
while(a[i]<=temp && i<j)
i++;
//交換兩個數(shù)在數(shù)組中的位置
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最終將基準數(shù)歸位
a[left]=a[i];
a[i]=temp;
quicksort(a, left,i-1);//繼續(xù)處理左邊的缤至，這里是一個遞歸的過程
quicksort(a, i+1,right);//繼續(xù)處理右邊的 ，這里是一個遞歸的過程
}
也可以這么寫：
/**
* 快排
* @param arr
* @param low
* @param high
* @return
*/
public static int[] quit(int arr[], int low, int high) {
int l = low;
int h = high;
int key = arr[l]; //先找出一個數(shù)作為基準數(shù)（這里取數(shù)組最中間的一位）
while (l < h) {
while (l < h && arr[h] >= key) h --; //從后向前：尋找比基準數(shù)小的數(shù)據(jù)康谆，如果找到领斥，停下來
if (l < h) { //“探測”到了符合要求的數(shù)據(jù)，則交換數(shù)據(jù)沃暗，繼續(xù)順著方向?qū)ふ? arr[l] = arr[h];
l ++;
}
while (l < h && arr[l] <= key) l ++; //從前向后：尋找比基準數(shù)大的數(shù)據(jù)月洛，如果找到，停下來
if (l < h) { ////“探測”到了符合要求的數(shù)據(jù)描睦，則交換數(shù)據(jù)膊存，繼續(xù)順著方向?qū)ふ? arr[h] = arr[l];
h --;
}
}
arr[l] = key;
if (l > low) quit(arr, low, l - 1);
if (h < high) quit(arr, h + 1, high);
return arr;
}
