排序算法-快速排序
快速排序是由C.A.R.Hoare在1960年提出.对于大型数据,快速排序算法的性能是希尔排序的5到10倍.
快速排序是一种分而治之算法,它将素组划分成两部分,然后分别对两个部分进行排序.
1.选则最右则的元素作为划分元素v,然后从左则扫描小于v的元素,然后从右则扫描大于v的元素.
交换那些使扫描停止的元素.
2.重复进行这样的过程直到两个指针相遇.
3.然后分别对左右两步分进行递归处理.最终得到一个排好序的数组.
下面给出C代码的实现.
// 划分算法
//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;
}
//快速排序
//a:数组
//l:数组的左则索引
//r:数组的右则索引
void quicksort(int a[],int l,int r)
{
int i;
if(l<=0)
return ;
quicksort(a,l, i-1);
quicksort(a,i+1,r);
}
//快速排序
//a:数组
//c:数组的长度
void quicksort(int a[],int c)
{
quicksort(a,0,c-1);
}
