快速排序代码大全介绍
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分两步处理：分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
代码如下：
template<classT>
voidSwap(T&a,T&b)
{
Tt;
t=a;
a=b;
b=t;
}
intMedian3(inta[],intstart,intend)
{
intmid=(start+end)/2;
if(a[start]>a[mid])
Swap(a[start],a[mid]);
if(a[mid]>a[end])
Swap(a[mid],a[end]);
if(a[start]>a[mid])
Swap(a[start],a[mid]);
Swap(a[mid],a[end-1]);
returna[end-1];
}
voidQuickSort(inta[],intstart,intend)
{
staticconstintCUTOFF=16;
if(end-start<CUTOFF)
{
InsertionSort(a,start,end);
return;
}
intm=Median3(a,start,end);
inti=start;
intj=end-1;
while(true)
{
while(a[++i]<m);
while(a[--j]>m);
if(i<j)
Swap(a[i],a[j]);
else
break;
}
Swap(a[i],a[end-1]);
QuickSort(a,start,i-1);
QuickSort(a,i+1,end);
}
voidSwap(T&a,T&b)
{
Tt;
t=a;
a=b;
b=t;
}
intMedian3(inta[],intstart,intend)
{
intmid=(start+end)/2;
if(a[start]>a[mid])
Swap(a[start],a[mid]);
if(a[mid]>a[end])
Swap(a[mid],a[end]);
if(a[start]>a[mid])
Swap(a[start],a[mid]);
Swap(a[mid],a[end-1]);
returna[end-1];
}
voidQuickSort(inta[],intstart,intend)
{
staticconstintCUTOFF=16;
if(end-start<CUTOFF)
{
InsertionSort(a,start,end);
return;
}
intm=Median3(a,start,end);
inti=start;
intj=end-1;
while(true)
{
while(a[++i]<m);
while(a[--j]>m);
if(i<j)
Swap(a[i],a[j]);
else
break;
}
Swap(a[i],a[end-1]);
QuickSort(a,start,i-1);
QuickSort(a,i+1,end);
}
本文地址：http://www.45fan.com/a/question/66893.html