/////////////////////快速排序,時(shí)間復(fù)雜度為O(nlog2n)///////////////////////
template<class T>
int Partion(T a[],int i,int j)//劃分函數(shù)
{
T temp;
temp=a[i];
while(i<j)
{
while(i<j && temp<=a[j])
j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j && a[i]<=temp)
i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
return i;
}
template <class T>
void qsort(T a[],int l,int h)
{
int m;
if(l<h)
{
m=Partion(a,l,h);
qsort(a,l,m-1);
qsort(a,m+1,h);
}
}
template<class T>
void SortWizard<T>::QuickSort()
{
qsort(a,0,n-1);
}
/**/////////////////////QuickSort_O(nlog2n)////////////////////////
/**////////////////////////歸并排序,時(shí)間復(fù)雜度O(nlog2n)/////////////////////////////
template <class T>
void Merge(T sr[],T tr[],int l,int m,int n)
{
int i,j,k;
i=l;
j=m+1;
k=l-1;
while(i<=m && j<=n)
{
if(sr[i]<sr[j])
tr[++k]=sr[i++];
else
tr[++k]=sr[j++];
}
while(i<=m)
tr[++k]=sr[i++];
while(j<=n)
tr[++k]=sr[j++];
for(i=l;i<=n;i++)
sr[i]=tr[i];
}
template <class T>
void Msort(T a[],T st[],int s,int t)
{
int m;
if(s<t)
{
m=(s+t)>>1;
Msort(a,st,s,m);
Msort(a,st,m+1,t);
Merge(a,st,s,m,t);
}
}
template <class T>
void SortWizard<T>::MergeSort()
{
T *st=new T[n];
Msort(a,st,0,n-1);
delete [ ]st;
}
/**//**//**///////////////////////MergeSort_O(nlog2n)///////////////////////////////