六种排序的C++实现

class SortNum   
{  
public:  
 SortNum();  
 virtual ~SortNum();  
    void exchange(int& b,int& c);//交换数据  
    void listout(int a[],int n);//列出所有  
 void selectSort(int a[],int n);//选择  
 void bublbleSort(int a[],int n);//冒泡  
 void insertSort(int a[],int n);//插入  
 void baseSort(int a[],int n);//基数  
 void quickSort(int a[],int n,int left,int right);//快速  
   
 void Merge(int *SR, int *TR, int i, int m, int n);//归并  
 void Msort( int *SR, int *TR1, int s, int t );  
 void Copy( int *S, int *T, int s, int t );  
}; 
#include "SortNum.h"  
#include "iostream.h"  
//////////////////////////////////////////////////////////////////////  
// Construction/Destruction  
//////////////////////////////////////////////////////////////////////  
  
SortNum::SortNum()  
{  
   
  
}  
  
SortNum::~SortNum()  
{  
  
}  
  
//交换两个元素  
void SortNum::exchange(int& b,int& c)  
{  
 int tem;  
 tem=b;  
 b=c;  
 c=tem;  
}  
//输出数组所有元素  
void SortNum::listout(int a[],int n)  
{  
 for(int i=0;i<n;i++)  
  cout <<a[i]<<" ";  
 cout <<endl;  
}  
  
  
//选择排序  
void SortNum::selectSort(int a[],int n)  
{  
 for(int i=0;i<n-1;i++)  
  {  
   int k=i;  
   for(int j=i+1;j<n;j++)  
    if(a[j]<a[k])  
     k=j;  
   exchange(a[i],a[k]);  
   listout(a,n);  
     
  }  
}  
//冒泡排序  
void SortNum::bublbleSort(int a[],int n)  
{  
 for(int i=n;i>1;i--)  
   for(int j=0;j<i-1;j++)  
   {  
    if(a[j]>a[j+1])  
    {  
     exchange(a[j],a[j+1]);  
     listout(a,n);  
       
    }  
   }  
}  
//插入排序  
void SortNum::insertSort(int a[],int n)  
{  
 for(int i=1;i<n;i++)//从第二个元素开始  
  {  
   int tem=a[i];  
   int j;  
   for(j=i-1;j>=0 && tem<a[j];j--)//判断比其小的,因为前面已经排好序列了,所以可以比,然后后退  
    a[j+1]=a[j];  
   a[j+1]=tem;//插入  
   listout(a,n);  
    
  }  
}  
//基数排序  
void SortNum::baseSort(int a[],int n)  
{  
      int r=10;//基数为十  
   int tem=1;  
    
    
   int max=a[0];  
   for(int i=0;i<n;i++)//找出最大的,以在while中确定结束的时机  
   {  
    if(a[i]>max)  
     max=a[i];  
   }  
  while((max%r)/tem !=0)//若最大的运算完为0.则整个基数排序结束  
  {  
   for(int i=n;i>1;i--)  
    for(int j=0;j<i-1;j++)  
    {  
     if((a[j]%r)/tem>(a[j+1]%r)/tem)  
     {  
      exchange(a[j],a[j+1]);  
        
     }  
    }  
   listout(a,n);  
    
   tem *=10;  
   r *=10;  
   
  }  
  
}  
//快速排序  
void SortNum::quickSort(int a[],int n,int left,int right)  
{  
      int i,j;  
  i=left;  
  j=right;  
  int middle=a[(left+right)/2];  
  do  
  {  
   while(a[i]<middle && i<right)//在左右找出一对,然后交换  
    i++;                        //问1:没成对怎么办?只有一个比中间小的,怎么弄?  
  
                                //知道的吼!!  
   while(a[j]>middle && j>left)  
    j--;  
   if(i<=j)  
   {  
    exchange(a[i],a[j]);  
    i++;  
    j--;  
    listout(a,n);//输出有些问题,递归调用中也输出???  
      
   }  
  }while(i<=j);  
     
  if(left<j)//递归调用排序左右两边,级级深入  
   quickSort(a,n,left,j);  
  if(right>i)  
   quickSort(a,n,i,right);  
}  
//归并排序  
//二路归并   问题~~无法输出详细过程  
void SortNum::Merge(int *SR, int *TR, int i, int m, int n){  
  
    // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]  
  
    int j = m+1;  
  
    int k = i;  
  
    for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中  
  
        if (SR[i]<=SR[j]){  
  
            TR[k] = SR[i++];  
  
        }else{  
  
            TR[k] = SR[j++];  
  
        }  
  
    }  
  
    while (i<=m) TR[k++] = SR[i++];   // 将剩余的 SR[i..m] 复制到TR  
  
    while (j<=n) TR[k++] = SR[j++];   // 将剩余的 SR[j..n] 复制到TR  
  
}//Merge  
  
void SortNum::Msort( int *SR, int *TR1, int s, int t ){  
  
    // 对SR[s..t]进行归并排序,排序后的记录存入TR1[s..t]  
  
    if (s==t){  
  
        TR1[s] = SR[s];  
  
    }else {  
  
         
        int TR2[7];//注:若main中数组改这里一定要改~~~~  
        int m = (s+t)/2;   // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]  
  
        Msort(SR,TR2,s,m);  // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]  
  
        Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]  
  
        Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]  
      Copy(SR,TR1,s,t);  
  
    }// else  
  
} // Msort  
void SortNum::Copy( int *S, int *T, int s, int t )  
{  
    for(int i=s;i<=t;i++)  
  S[i]=T[i];  
    listout(S,7);  
}  
  
   
  
  
void main()  
{  
 int a[7]={81,129,655,543,987,26,794};//问题:数组中了length怎么解决  
 SortNum so;  
 cout <<"原始数据"<<endl;  
 so.listout(a,7);  
 //so.exchange(a[0],a[1]);//测试exchange方法  
 //so.listout(a,7);  
    cout <<"选择排序类型:1.选择,2.冒泡,3.插入,4.基数 5.快速 6.归并"<<endl;  
 int n;  
 cin >>n;  
 int b[7];  
 switch( n)  
 {   
  case 1:so.selectSort(a,7);break;  
  case 2:so.bublbleSort(a,7);break;  
  case 3:so.insertSort(a,7);break;  
  case 4:so.baseSort(a,7);break;  
  case 5:so.quickSort(a,7,0,6);break;  
  case 6:so.Msort(a,b,0,6);break;  
  
 }  
   
}