排序算法综合：有直接插入排序，希尔排序，快速排序，归并排序等

#define CPP C++
#define MPP M++
#define MP2 M+=2
#define MP3 M+=3

#include
#include 
#include
#include 
#include 
#include

const int maxsize=1000;
typedef int datatype;
typedef struct{
	datatype key;
}rectype;
typedef rectype list[maxsize+1];      //排序表类型，0号单元不用

__int64 CM;                 //比较和移动次数

void check（list Rint n） {   //检验排序结果
  int i;
  for（i=2;i<=n;i++）
    if（R[i].key  cout<<“Correct! “<}

void disp（list Rint n） {    //显示数组中的数据
  int i;
  for（i=1;i<=n;i++） {
    cout<  }
  cout<}

/*int random1（int num） {return rand（）;} //0~RAND_MAX=32767

int random2（int num） {//素数模乘同余法0~M
  int A=16807;      // 1680739722040764261123630360016  48271?
  int M=2147483647; //有符号4字节最大素数2^31-1
  int Q=M/A;
  int R=M%A;
  static int x=1;   //seed（set to 1）
  int x1;
  x1=A*（x%Q）-R*（x/Q）;
  if（x1>=0） x=x1;
  else      x=x1+M;
  return x;
}*/

void InsertSort（list R int n）  {  //有监视哨，直接插入排序
int ij;
  for（i=2;i<=n;i++） {           //依次插入R[2]R[3]…R[n]
    if（CPPR[i].key>=R[i-1].key） continue;
                                //R[i]大于有序区最后一个记录，则本趟不需插入
    MPPR[0]=R[i];              //R[0]是监视哨
    j=i-1;
    do {                        //查找R[i]的插入位置
      MPPR[j+1]=R[j];j--;      //记录后移，继续向前搜索
    } while（CPPR[0].key    MPPR[j+1]=R[0];            //插入R[i]
  }
}

void InsertSort0（list R int n）{//直接插入排序，无监视哨
  int ij;rectype x;            //x为辅助量（用R[0]代替时间变长）
  for（i=2;i<=n;i++） {           //进行n-1次插入
    if（CPPR[i].key>=R[i-1].key） continue;
    MPPx=R[i];                 //待排记录暂存到x
    j=i-1;
    do {                        //顺序比较和移动
      MPPR[j+1]=R[j];j--;
    } while（j>=1 && （CPPx.key    MPPR[j+1]=x;               //插入R[i]
  }
}

void Shellinsert（list R int n int h）{      //shell排序的一趟排序过程，h为增量
	  int ijk;
	  for（i=1;i<=h;i++）	{	
    for（j=i+h;j<=n;j+=h） {
      if（CPPR[j].key>=R[j-h].key） continue;
      MPPR[0]=R[j];	
      k=j-h;		
      do {		
       MPP R[k+h]=R[k];k=k-h;
      } while（k>0 &&（CPP R[0].key      MPP R[k+h]=R[0];
    }

}
}

void ShellSort（list Rint nint d[]int t）{      //d[]为增量序列，t为增量序列长度
	int i;
   for（i=0;i      Shellinsert（Rnd[i]）;
}

void BubbleSort（list Rint n） {//上升法冒泡排序
  int ijflag;rectype x;       //x为辅助量（可用R[0]代替）
  for（i=1;i<=n-1;i++） {         //做n-1趟扫描
    flag=0;                     //置未交换标志
    for（j=n;j>=i+1;j--）         //从下向上扫描
      if（CPPR[j].key        flag=1;
        MP3x=R[j];R[j]=R[j-1];R[j-1]=x;//交换 
      }
    if（!flag） break;            //本趟未交换过记录，排序结束
  }
}




void BubbleSort0（list R int n）{            //下沉法冒泡排序
int ijflag;rectype x;       //x为辅助量（可用R[0]代替）
  for（i=1;i<=n-1;i++） {         //做n-1趟扫描
    flag=0;                     //置未交换标