qsort

void qsort(int[] a,int p,int r){
    if(p<r){
    int q=partition(a,p,r);
    qsort(p,q-1);
    qsort(q+1,r);
}
    return;
}

int partition(int[] a,int p,int r){
    int i=p;j=r+1;
    int x=a[p];
    while(true){
        while(a[++i]<x&&i<r);
        while(a[++j]>x);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}//qsort(a,0,a.length)

p，r是要排的起止位置，把數(shù)組分成三塊，a[p:q-1]都比a[q]小，a[q+1:r]都比a[q]大。q是不定的下標，要通過分治去找，找的過程中先隨便選一個參照值，按標準選第一個。然后i從第二個到最后，j從最后到第一推進。先找到一個大于等于基準的i然后再找一個小于等于基準的j，交換它們對應數(shù)組元素的值。當i>=j時(如果找ij的時候用嚴格不等式，那么i永遠不會=j)，此時a[j]還小于a[p]，交換它們的值，現(xiàn)在數(shù)組就分成三塊，再返回基準元素的下標。這一批粗糙的處理就結(jié)束。
三步：分解，遞歸，合并。分解由partition來，遞歸qsort，這個搞法中每次分解完后就已經(jīng)合并。

一些結(jié)束條件：
無元素：沒有起止下標，函數(shù)不能調(diào)用
一個元素：不滿足p<r，已經(jīng)有序直接返回，一次結(jié)束。
兩個元素：有序，ij都=1，調(diào)用qsort(1,-1)。倒序，i=1,j=0,調(diào)用qsort(1,0)。兩層遞歸，最后一層遞歸不做事只作為出口。
三個元素：順序，倒序要三層遞歸才能排完，亂序反而只要兩層。
從上面知道，每次用q把數(shù)組割開左右兩塊時，如果有一邊沒有元素，就等于沒有利用分治法，原數(shù)組越有序排得就越慢。如果每次q的位置都正好把兩邊分得均勻，那效率就會很高。基準元素可以不選第一個元素，隨機選一個，i和j兩邊夾的時候跳過這個位置，最后換的時候基準如果在右邊那塊就要和a[i]換而不是a[j]。