//排序精靈
//Copyright:abilitytao,Nanjing University Of Science And Technology
/**//////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
template<class T>
class SortWizard
{
private:
T *a;
int n;
public:
SortWizard(){ a=NULL;n=0;}
SortWizard(T *a,int n){this->a=a;this->n=n;}
void Set(T *a,int n){this->a=a;this->n=n;}
void InsertSort();
void ShellSort();
void BubbleSort();
void QuickSort();
void SelectSort();
void MergeSort();
void HeapSort();
};
template<class T>
void SortWizard<T>:: InsertSort()//直接插入排序,時間復(fù)雜度為O(n^2)
{
int i,j;
T temp;
for(i=1;i<n;i++)
{
temp=a[i];
for(j=i-1;j>=0;j--)
{
if(temp<a[j])
a[j+1]=a[j];
else
break;
}
a[j+1]=temp;
}
}
template<class T>
void SortWizard<T>::ShellSort()//希爾排序,時間復(fù)雜度為O(n^1.5)
{
int i,j,d;
T temp;
d=n>>1;
while(d>=1)
{
for(i=d;i<n;i++)
{
temp=a[i];
for(j=i-d;j>=0;j-=d)
{
if(a[j]>temp)
a[j+d]=a[j];
else
break;
}
a[j+d]=temp;
}//這個while實際上是直接插入排序
d>>=1;//即d右移一位，d除以2；
}
}//ShellSort
template<class T>
void SortWizard<T>::BubbleSort()//冒泡排序,時間復(fù)雜度為O(n^2)
{
int i,j;
T temp;
for(i=n-1;i>0;i--)
{
for(j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
/**//////////////////////快速排序,時間復(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)////////////////////////
template <class T>
void SortWizard<T>::SelectSort()//選擇排序，時間復(fù)雜度為O(n^2)
{
int i,j,k;
T temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[k])
k=j;
}
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
/**////////////////////////堆排序////////////////////////////template <class T>
void Sift(T a[],int k,int m)//k篩選標(biāo)號，m篩選范圍
{
int i,j;
T temp;
i=k;
j=2*i+1;//j指向左兒子;
temp=a[i];//暫存a[i];
while(j<=m)
{
if(j<m &&a[j]<a[j+1])
j++;
if(temp<a[j])
{
a[i]=a[j];
i=j;
(j<<=1)++;//j*2+1
}
else
break;
}
a[i]=temp;
}
template <class T>
void SortWizard<T>::HeapSort()//堆排序，建堆時間復(fù)雜度O(n)，篩選O(nlog2n);
{
int i;
T temp;
for(i=(n>>1)-1;i>=0;i--)
Sift(a,i,n-1);
for(i=n-1;i>=1;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
Sift(a,0,i-1);
}
}
/**//////////////////////HeapSort_O(nlog2n)///////////////////////////
///////////////////////歸并排序,時間復(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)///////////////////////////////
/////////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////
int main ()
{
SortWizard<double>test;
double test1[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test1,sizeof(test1)/sizeof(double));
test.InsertSort();
double test2[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test2,sizeof(test2)/sizeof(double));
test.ShellSort();
double test3[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test3,sizeof(test3)/sizeof(double));
test.BubbleSort();
double test4[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test4,sizeof(test4)/sizeof(double));
test.QuickSort();
double test5[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test5,sizeof(test5)/sizeof(double));
test.SelectSort();
double test6[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test6,sizeof(test6)/sizeof(double));
test.HeapSort();
double test7[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
test.Set(test7,sizeof(test7)/sizeof(double));
test.MergeSort();
return 0;
}
如果您認(rèn)為還可以改進的話 請留言告訴我:-)