paixu.txt

各种排序方法（冒泡排序

大家都知道的冒泡排序: 

＃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];
}