排序算法-快速排序(三者取中劃分)
快速排序算法的一個改進版本,在數組取三個元素的中間進行劃分.這樣可以避免出現最壞的情況.
取數組的左邊,中間,右邊的元素.對這三個數進行排序.
#define less(A,B) ((A)<(B)) // 小於比較
#define exch(A,B) {int temp=A; A=B; B=temp;} // 交換
#define compexch(A,B) if(less(A,B)) exch(A,B) // 小於則交換
下面給出C代碼的實現.
// 劃分算法
//a:數組
//l:數組的左則索引
//r:數組的右則索引
void quicksort(int a[],int l,int r)
{
int i;
int temp;
// a[(l+r)/2] 與 a[r-1]交換
exch(a[(l+r)/2], a[r-1]);
// 取數組的左邊,中間,右邊的元素.對這三個數進行排序.
// 小於則交換
compexch(a[r-1],a[l]);
compexch(a[r], a[l]);
compexch(a[r], a[r-1]);
i = partition(a,l+1,r-1);
quicksort(a[],l, i-1);
quicksort(a[],i+1,r);
}
// 劃分算法
//a:數組
//l:數組的左則索引
//r:數組的右則索引
int partition(int a[],int l,int r)
{
int i,j,v,t;
i = l;
j = r;
v = a[j];//選則最右則的元素作為劃分元素v
while(true)
{
while(a[i]<v)
++i;// i的左則小與v
while(v<a[j])
{
++j;// j的右則大與v
if(j==l)
break;// 跳出
}
if(i>=j)
break;// 兩個指針相遇跳出掃描.
// 交換i,j,交換那些使掃描停止的元素.
t=a[i];
a[i]=a[j];
a[j]=t;
}
// 交換i,r,保證v的左則小於於它,v的右則大於它.
t=a[i];
a[i]=a[r];
a[r]=t;
return i;
}