首先先介绍排序:
1,大家都知道的冒泡排序:
＃i nclude
＃i nclude
using namespace std;
template
void swap(type x[],int,int);
template
void BubbleSort(type x[],int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "< BubbleSort(x,n);
cout<<"\nAfter Sort:"< for(int i=0;i cout<<" "<;
system("pause");
return 0;
}
template
void BubbleSort(type x[],int n)
{
for(int i=n-1;i>=0;i--)
{ int flag=0;
for(int j=0;j if(x[ j]>x[ j+1])
{ swap(x,j,j+1);
flag=1;
}
if(flag==0)
return;
}
}
template
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
2,简单的选择排序
＃i nclude
＃i nclude
using namespace std;
template
void swap(type x[],int,int);
template
void SlectSort(type x[],int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "< SlectSort(x,n);
cout<<"\nAfter Sort:"< for(int i=0;i cout<<" "< system("pause");
return 0;
}
template
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
template
void SlectSort(type x[],int n)
{
for(int i=0;i {
for(int j=i+1;j if(x[ j] swap(x,i,j);
}
}
3,插入排序
＃i nclude
＃i nclude
using namespace std;
template
void swap(type x[],int,int);
template
void InsertSort(type x[],int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "<InsertSort(x,n);
cout<<"\nAfter Sort:"<for(int i=0;i cout<<" "<system("pause");
return 0;
}
template
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
template
void InsertSort(type x[],int n)
{
for(int i=1;i for(int j=i;j>0;j--)
if(x[ j] swap(x,j,j-1);
}
4:希尔排序
＃i nclude
＃i nclude
using namespace std;
template
void swap(type x[],int,int);
template
void ShellSort(type x[],int);
template
void ShellSorthelper(type x[],int,int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "<ShellSort(x,n);
cout<<"\nAfter Sort:"<for(int i=0;i cout<<" "<system("pause");
return 0;
}
template
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
template
void ShellSort(type x[],int n)
{
for(int i=n/2;i>=1;i/=2)
for(int j=0;j ShellSorthelper(&x[ j],i,n-j);
}
template
void ShellSorthelper(type x[],int len,int n)
{
for(int i=len;i for(int j=i;j>0;j-=len)
if(x[ j] swap(x,j,j-len);
}
5,快速排序
＃i nclude
＃i nclude
using namespace std;
template
void QuicklySort(type x[],int n);
template
void QuicklySorthelper(type x[],int,int);
template
void swap(type x[],int,int);
int main()
{
srand(time(0));
const int n=10;
int x[ n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "<QuicklySort(x,n);
cout<<"\nAfter Sort:"<for(int j=0;j cout<<" "<system("pause");
return 0;
}
template
void QuicklySort(type x[],int n)
{
QuicklySorthelper(x,0,n-1);
}
template
void QuicklySorthelper(type x[],int l,int r)
{ if(r>l)
{ swap(x,l,(l+r)/2);//尽量找出好的轴值;
int i=l;int j=r+1;type pivot=x[l];
while(i{
while(x[--j]>pivot && i if(i swap(x,i,j);
while(x[++i] if(i swap(x,i,j);
}
x[ i]=pivot;
QuicklySorthelper(x,l,i-1);
QuicklySorthelper(x,i+1,r);
}
}
template
void swap(type x[],int n,int m)
{
type temp=x[n];
x[n]=x[m];
x[m]=temp;
}
6,归并排序(2路)
＃i nclude
＃i nclude
using namespace std;
template
void swap(type x[],int,int);
template
void MegicSort(type x[],int);
template
void MegicSorthelper(type x[],type y[],int,int);
template
void MegicSortPass(type x[],type y[],int,int,int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i x[ i]=rand()%99;
for(int i=0;i cout<<" "<MegicSort(x,n);
cout<<"\nAfter Sort:"<for(int i=0;i cout<<" "<system("pause");
return 0;
}
template
void swap(type x[],int m,int n)
{
type temp=x[m];
x[m]=x[n];
x[n]=temp;
}
template
void MegicSort(type x[],int n)
{ type *y=new type[n];
int len=1;
while(len{
MegicSorthelper(x,y,len,n);len*=2;
MegicSorthelper(y,x,len,n);len*=2;
}
delete []y;
}
template
void MegicSorthelper(type x[],type y[],int len,int n)
{ int i;
for(i=0;i+2*len MegicSortPass(x,y,i,i+len,i+2*len);
if(i+len MegicSortPass(x,y,i,i+len,n);
else
for(;i y[ i]=x[ i];
}
template
void MegicSortPass(type x[],type y[],int l,int m,int n)
{
int i=l,j=m,k=l;
for(;i{
if(x[ i]>x[ j])
y[ k]=x[ j++];
else
y[ k]=x[ i++];
}
for(;i y[ k++]=x[ i];
for(;j y[ k++]=x[ j];
} 