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]。