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

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

#include
#include
#include
 
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]=pivotkey) {compCount++;--high;}
     Shift(data,data,low,high);
     compCount++;
     while(low0&&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=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>size;
    cout<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:n";
    RandomizeList();
    for(m=0;m<3;m++)
    {
      if(m==2) InverseOrder();
      cout<<"t";
      for(i=1;i<=size;i++) cout<>size;
     cout<<"请输入"<>data[i];
     CopyData(data,data2);
     out_stream<<"手动输入待排序表的各个算法的比较次数和移动次数如下:n";
     out_stream<<"tcompCounttshiftCountn";
     out_stream.close();
     cout<<"手动输入待排序表的各个算法的比较次数和移动次数如下:n";
     cout<<"tcompCounttshiftCountn";
     for(j=0;j>cmd;
     Interpret(cmd);
   }while(cmd!=4);
 }

以上就是本文所述的全部内容了，希望能够对大家熟悉掌握这十种排序算法有所帮助。