|
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<iostream>
#i nclude<cstdlib>
using namespace std;
template<class type>
void swap(type x[],int,int);
template<class type>
void InsertSort(type x[],int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i<n;i++)
x[ i]=rand()%99;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
InsertSort(x,n);
cout<<"\nAfter Sort:"<<endl;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
system("pause");
return 0;
}
template<class type>
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
template<class type>
void InsertSort(type x[],int n)
{
for(int i=1;i<n;i++)
for(int j=i;j>0;j--)
if(x[ j]<x[ j-1])
swap(x,j,j-1);
}
4:希尔排序 #i nclude<iostream>
#i nclude<cstdlib>
using namespace std;
template<class type>
void swap(type x[],int,int);
template<class type>
void ShellSort(type x[],int);
template<class type>
void ShellSorthelper(type x[],int,int);
int main()
{
srand(time(0));
const int n=10;
int x[n];
for(int i=0;i<n;i++)
x[ i]=rand()%99;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
ShellSort(x,n);
cout<<"\nAfter Sort:"<<endl;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
system("pause");
return 0;
}
template<class type>
void swap(type x[],int n,int m)
{ int temp=x[n];
x[n]=x[m];
x[m]=temp;
}
template<class type>
void ShellSort(type x[],int n)
{
for(int i=n/2;i>=1;i/=2)
for(int j=0;j<i;j++)
ShellSorthelper(&x[ j],i,n-j);
}
template<class type>
void ShellSorthelper(type x[],int len,int n)
{
for(int i=len;i<n;i+=len)
for(int j=i;j>0;j-=len)
if(x[ j]<x[ j-len])
swap(x,j,j-len);
}
5,快速排序 #i nclude<iostream>
#i nclude<cstdlib>
using namespace std;
template<class type>
void QuicklySort(type x[],int n);
template<class type>
void QuicklySorthelper(type x[],int,int);
template<class type>
void swap(type x[],int,int);
int main()
{
srand(time(0));
const int n=10;
int x[ n];
for(int i=0;i<n;i++)
x[ i]=rand()%99;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
QuicklySort(x,n);
cout<<"\nAfter Sort:"<<endl;
for(int j=0;j<n;j++)
cout<<" "<<x[ j];
system("pause");
return 0;
}
template<class type>
void QuicklySort(type x[],int n)
{
QuicklySorthelper(x,0,n-1);
}
template<class type>
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<j)
{
while(x[--j]>pivot && i<j);
if(i<j)
swap(x,i,j);
while(x[++i]<pivot && i<j);
if(i<j)
swap(x,i,j);
}
x[ i]=pivot;
QuicklySorthelper(x,l,i-1);
QuicklySorthelper(x,i+1,r);
}
}
template<class type>
void swap(type x[],int n,int m)
{
type temp=x[n];
x[n]=x[m];
x[m]=temp;
}
6,归并排序(2路) #i nclude<iostream>
#i nclude<cstdlib>
using namespace std;
template<class type>
void swap(type x[],int,int);
template<class type>
void MegicSort(type x[],int);
template<class type>
void MegicSorthelper(type x[],type y[],int,int);
template<class type>
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<n;i++)
x[ i]=rand()%99;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
MegicSort(x,n);
cout<<"\nAfter Sort:"<<endl;
for(int i=0;i<n;i++)
cout<<" "<<x[ i];
system("pause");
return 0;
}
template<class type>
void swap(type x[],int m,int n)
{
type temp=x[m];
x[m]=x[n];
x[n]=temp;
}
template<class type>
void MegicSort(type x[],int n)
{ type *y=new type[n];
int len=1;
while(len<n)
{
MegicSorthelper(x,y,len,n);len*=2;
MegicSorthelper(y,x,len,n);len*=2;
}
delete []y;
}
template<class type>
void MegicSorthelper(type x[],type y[],int len,int n)
{ int i;
for(i=0;i+2*len<n;i+=2*len)
MegicSortPass(x,y,i,i+len,i+2*len);
if(i+len<n)
MegicSortPass(x,y,i,i+len,n);
else
for(;i<n;i++)
y[ i]=x[ i];
}
template<class type>
void MegicSortPass(type x[],type y[],int l,int m,int n)
{
int i=l,j=m,k=l;
for(;i<m && j<n;k++)
{
if(x[ i]>x[ j])
y[ k]=x[ j++];
else
y[ k]=x[ i++];
}
for(;i<m;i++)
y[ k++]=x[ i];
for(;j<n;j++)
y[ k++]=x[ j];
} |
|
|
