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是要排的起止位置，把数组分成三块，a[p:q-1]都比a[q]小，a[q+1:r]都比a[q]大。q是不定的下标，要通过分治去找，找的过程中先随便选一个参照值，按标准选第一个。然后i从第二个到最后，j从最后到第一推进。先找到一个大于等于基准的i然后再找一个小于等于基准的j，交换它们对应数组元素的值。当i>=j时(如果找ij的时候用严格不等式，那么i永远不会=j)，此时a[j]还小于a[p]，交换它们的值，现在数组就分成三块，再返回基准元素的下标。这一批粗糙的处理就结束。
三步：分解，递归，合并。分解由partition来，递归qsort，这个搞法中每次分解完后就已经合并。

一些结束条件：
无元素：没有起止下标，函数不能调用
一个元素：不满足p<r，已经有序直接返回，一次结束。
两个元素：有序，ij都=1，调用qsort(1,-1)。倒序，i=1,j=0,调用qsort(1,0)。两层递归，最后一层递归不做事只作为出口。
三个元素：顺序，倒序要三层递归才能排完，乱序反而只要两层。
从上面知道，每次用q把数组割开左右两块时，如果有一边没有元素，就等于没有利用分治法，原数组越有序排得就越慢。如果每次q的位置都正好把两边分得均匀，那效率就会很高。基准元素可以不选第一个元素，随机选一个，i和j两边夹的时候跳过这个位置，最后换的时候基准如果在右边那块就要和a[i]换而不是a[j]。