C++中十种内部排序算法的比较分析

#include<iostream>#include<ctime>#include<fstream> using namespace std;#define MAXSIZE 1000  //可排序表的最大长度#define SORTNUM 10   //测试10中排序方法#define max 100    //基数排序时数据的最大位数不超过百位； typedef struct node {  int data3;  int next;} node;typedef int DataType[MAXSIZE+2];DataType data;DataType data2;DataType R1;int size;//可排序表的长度int head;int fr[10];int re[10];long compCount;//统计比较次数long shiftCount;//统计移动次数  void BeforeSort()//对比较次数和移动次数清零 {   compCount=0;   shiftCount=0; } bool Less(int i,int j)//若表中第i个元素小于第j个元素，则返回True，否则返回False {   compCount++;   return data[i]<data[j]; }  void Swap(int i,int j)//交换表中第i个和第j个元素 {   int a;   a=data[i];   data[i]=data[j];   data[j]=a;   shiftCount=shiftCount+3; }  void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i] {   R[i]=R2[j];   shiftCount++; }  void CopyData(DataType list1,DataType list2) {   int i;   for(i=1;i<=size;i++) list2[i]=list1[i];    }  void InverseOrder()//将可排序表置为逆序 {   int i,j;   for(i=1,j=size;i<=size/2;i++,j--)   {     int a;     a=data[i];     data[i]=data[j];     data[j]=a;   }   CopyData(data,data2); }  void RandomizeList()//由系统随机一组数 {   int i;   srand(time(0));   for(i=1;i<=size;i++)     data[i]=rand()%(size+1);   CopyData(data,data2);    ofstream out_stream;   out_stream.open("input.txt",ios::app);   if(out_stream.fail())   {     cout<<"input file opening failed./n";     exit(1);   }   for(i=1;i<=size;i++) out_stream<<data[i]<<" ";   out_stream<<"/n";   out_stream.close();  } void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表 {   CopyData(data2,data); }  void output()//输出函数 {   ofstream out_stream;   cout<<"/t"<<compCount<<"/t/t"<<shiftCount<<"/n";   out_stream.open("output.txt",ios::app);   if(out_stream.fail())   {     cout<<"Output file opening failed./n";     exit(1);   }   out_stream<<"/t"<<compCount<<"/t/t"<<shiftCount<<"/n";   out_stream.close();    }  void BubbleSort()//冒泡排序 {   BeforeSort();   int swapped,i,m;   m=size-1;   do{     swapped=0;     for(i=1;i<=m;i++)     {       if(Less(i+1,i))        {         Swap(i+1,i);         swapped=1;       }     }     m--;   }while(swapped);   output(); }  void InsertSort() //插入排序 {   BeforeSort();   int i,j;   for(i=2;i<=size;i++)   {     Shift(data,data,0,i);     j=i-1;     while(Less(0,j))      {       Shift(data,data,j+1,j);       j--;     }     Shift(data,data,j+1,0);   }   output(); }  void SelectSort()//选择排序 {   BeforeSort();   int i,j,min;   for(i=1;i<=size-1;i++)   {     min=i;     for(j=i+1;j<=size;j++)       if(Less(j,min)) min=j;     if(i!=min) Swap(i,min);   }   output(); }  int Partition(int low,int high) {   int pivotkey;   Shift(data,data,0,low);   pivotkey=data[low];   while(low<high)   {     compCount++;     while(low<high&&data[high]>=pivotkey) {compCount++;--high;}     Shift(data,data,low,high);     compCount++;     while(low<high&&data[low]<=pivotkey) {compCount++;++low;}     Shift(data,data,high,low);   }   Shift(data,data,low,0);   return low;  }  void QSort(int low,int high)//QuickSort的辅助函数 {   int pivotloc;   if(low<high)   {     pivotloc=Partition(low,high);     QSort(low,pivotloc-1);     QSort(pivotloc+1,high);   } }  void QuickSort()//快速排序 {   BeforeSort();   QSort(1,size);   output(); }  void ShellSort()//希尔排序 {   BeforeSort();   int i,j,h;   i=4;   h=1;   while(i<=size)    {     i=i*2;     h=2*h+1;   }   while (h!=0)   {     i=h;     while(i<=size)     {       j=i-h;       while(j>0&&Less(j+h,j))       {         Swap(j,j+h);         j=j-h;       }       i++;     }     h=(h-1)/2;   }   output(); }  void Sift(int left,int right)//堆排序的调堆函数 {   int i,j,finished=0;   i=left;   j=2*i;   Shift(data,data,0,left);   Shift(data,data,MAXSIZE+1,left);   while(j<=right&&!finished)   {     if(j<right&&Less(j,j+1)) j=j+1;     if(!Less(0,j)) finished=1;     else     {       Shift(data,data,i,j);       i=j;       j=2*i;     }   }   Shift(data,data,i,MAXSIZE+1); }  void HeapSort()//堆排序 {   int left,right;   BeforeSort();   for(left=size/2;left>=1;left--) Sift(left,size);   for(right=size;right>=2;right--)   {     Swap(1,right);     Sift(1,right-1);   }   output();   } void BInsertSort()//折半插入排序{  BeforeSort();  int i,low,high,m,j;  for(i=2;i<=size;i++)  {    Shift(data,data,0,i);    low=1;    high=i-1;    while(low<=high)    {      m=(low+high)/2;      if(Less(0,m)) high=m-1;      else low=m+1;    }    for(j=i-1;j>=high+1;j--) Shift(data,data,j+1,j);    Shift(data,data,high+1,0);     }  output();} void Binsort()//2-路插入排序{ BeforeSort(); int i,k,j; int first,last; first=last=1; Shift(R1,data,1,1); for(i=2;i<=size;i++) {   compCount++;   if(data[i]>=R1[1])   {     compCount++;     j=last;     while(j>=1&&R1[j]>data[i])     {       Shift(R1,R1,j+1,j);       j--;       compCount++;     }     Shift(R1,data,j+1,i);     last++;   }   else   {     first--;     if(first==0) first=size;     j=first+1;     compCount++;     while(j<=size&&R1[j]<=data[i])     {       Shift(R1,R1,j-1,j);       j++;       compCount++;     }     Shift(R1,data,j-1,i);   } } k=1; j=first; while(k<=size) {  Shift(data,R1,k,j);  k++;  j=(j+1)%(size+1);  if(j==0) j=j+1; } output();} void Merge(int low,int m,int high){   int i=low,j=m+1,p=1;    while(i<=m&&j<=high)    {     if(Less(i,j)) Shift(R1,data,p++,i++);     else Shift(R1,data,p++,j++);   }   while(i<=m)      Shift(R1,data,p++,i++);   while(j<=high)      Shift(R1,data,p++,j++);    for(p=1,i=low;i<=high;p++,i++)     Shift(data,R1,i,p);  } void MSort(int low, int high) { int mid;  if (low<high){      mid=(low+high)/2;     MSort(low, mid);     MSort(mid+1,high);    Merge(low, mid, high);  } }  void MergeSort()//归并排序{  BeforeSort();  MSort(1,size);  output();} void Distribute(node *a, int w){  int i;  for (i=0; i<10; i++) fr[i] = -1;  for (i=head; i!=-1; i=a[i].next)   {    int x = a[i].data3 / w % 10;    if (fr[x] == -1)     {      fr[x] = re[x] = i;      compCount++;    }    else    {      a[re[x]].next = i;      re[x] = i;      shiftCount++;    }  }  for (i=0; i<10; i++)  {    if (fr[i] != -1)     {      a[re[i]].next = -1;    }  }} void Collect(node *a){  int i, last;   last = -1;  for (i=0; i<10; i++)   {    if (fr[i] != -1)     {      if (last == -1)      {        head = fr[i];        last = re[i];      }      else {        a[last].next = fr[i];        last = re[i];        shiftCount++;      }    }  }  a[last].next = -1;} void RadixSort()//基数排序算法。{  BeforeSort();  ofstream out_stream;  node* a;  a=new node[size];  int i,j=1;  for (i=0; i<size; i++) {    a[i].data3=data[i+1];    a[i].next = i + 1;  }  head = 0;  a[size-1].next = -1;  for (i=1; i<=max; i*=10) {    Distribute(a, i);    Collect(a);   }  cout<<"/t"<<compCount<<"/t/t"<<shiftCount<<"/n";  while (head != -1)   {    data[j++]=a[head].data3;    head = a[head].next;  }  CopyData(data,data2);     cout<<"/n";  out_stream.open("output.txt",ios::app);  out_stream<<"/t"<<compCount<<"/t/t"<<shiftCount<<"/n/n";  out_stream.close(); } void Initialization()//系统初始化{  system("cls");//清屏  cout<<"***************************************************************************/n"    <<"***************** 《内部排序算法的比较》 ********************************/n"    <<"***************************************************************************/n"    <<"************************ *主菜单* ***************************************/n"    <<"******* 1.由系统随机产生待排序表 ****************************************/n"    <<"******* 2.手动输入待排序表 **********************************************/n"    <<"******* 3.返回主菜单 ****************************************************/n"    <<"******* 4.退出程序 ******************************************************/n"    <<"***************************************************************************/n"    <<"请输入要执行的步骤：";}  void Interpret(int cmd)//调用各个算法 {   int i,j,m;   ofstream out_stream;   out_stream.open("output.txt",ios::app);   if(out_stream.fail())   {     cout<<"Output file opening failed./n";     exit(1);   }   switch(cmd)   {   case 1:         out_stream<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:/n";    out_stream<<"/tcompCount/tshiftCount/n";    out_stream.close();    cout<<"请输入待排序表的长度:";    cin>>size;    cout<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:/n";    RandomizeList();    for(m=0;m<3;m++)    {      if(m==2) InverseOrder();      cout<<"/t";      for(i=1;i<=size;i++) cout<<data[i]<<" ";      cout<<"/n";      cout<<"/tcompCount/tshiftCount/n";          for(j=0;j<SORTNUM;j++)      {        RecallList();        out_stream.open("output.txt",ios::app);        if(j==0) {cout<<"Bubbl: ";out_stream<<"Bubbl: ";out_stream.close();BubbleSort();}        if(j==1) {cout<<"Tnser: ";out_stream<<"Tnser: ";out_stream.close();InsertSort();}        if(j==2) {cout<<"Selec: ";out_stream<<"Selec: ";out_stream.close();SelectSort();}        if(j==3) {cout<<"Quick: ";out_stream<<"Quick: ";out_stream.close();QuickSort();}        if(j==4) {cout<<"Shell: ";out_stream<<"Shell: ";out_stream.close();ShellSort();}        if(j==5) {cout<<"Heap : ";out_stream<<"Heap : ";out_stream.close();HeapSort();}        if(j==6) {cout<<"BInse: ";out_stream<<"BInse: ";out_stream.close();BInsertSort();}        if(j==7) {cout<<"Merge: ";out_stream<<"Merge: ";out_stream.close();MergeSort();}        if(j==8) {cout<<"Bin : ";out_stream<<"Bin : ";out_stream.close();Binsort();}        if(j==9) {cout<<"Radix: ";out_stream<<"Radix: ";out_stream.close();RadixSort();}                        }}           //}         break;   case 2:          cout<<"请输入待排序表的长度：";     cin>>size;     cout<<"请输入"<<size<<"个数据:/n";     for(i=1;i<=size;i++) cin>>data[i];     CopyData(data,data2);     out_stream<<"手动输入待排序表的各个算法的比较次数和移动次数如下:/n";     out_stream<<"/tcompCount/tshiftCount/n";     out_stream.close();     cout<<"手动输入待排序表的各个算法的比较次数和移动次数如下:/n";     cout<<"/tcompCount/tshiftCount/n";     for(j=0;j<SORTNUM;j++)      {        RecallList();        out_stream.open("output.txt",ios::app);        if(j==0) {cout<<"Bubbl: ";out_stream<<"Bubbl: ";out_stream.close();BubbleSort();}        if(j==1) {cout<<"Tnser: ";out_stream<<"Tnser: ";out_stream.close();InsertSort();}        if(j==2) {cout<<"Selec: ";out_stream<<"Selec: ";out_stream.close();SelectSort();}        if(j==3) {cout<<"Quick: ";out_stream<<"Quick: ";out_stream.close();QuickSort();}        if(j==4) {cout<<"Shell: ";out_stream<<"Shell: ";out_stream.close();ShellSort();}        if(j==5) {cout<<"Heap : ";out_stream<<"Heap : ";out_stream.close();HeapSort();}        if(j==6) {cout<<"BInse: ";out_stream<<"BInse: ";out_stream.close();BInsertSort();}        if(j==7) {cout<<"Merge: ";out_stream<<"Merge: ";out_stream.close();MergeSort();}        if(j==8) {cout<<"Bin : ";out_stream<<"Bin : ";out_stream.close();Binsort();}        if(j==9) {cout<<"Radix: ";out_stream<<"Radix: ";out_stream.close();RadixSort();}       }     break;   case 3:     Initialization();     break;   }  }  void main() {   Initialization();   int cmd;   do{     cin>>cmd;     Interpret(cmd);   }while(cmd!=4); }