C++实现：冒泡排序--希尔排序--快速排序--堆--归并排序

# include stdio.h# include stdlib.h# include time.h# include windows.h# define OK 1# define ERROR 0# define TRUE 1# define FALSE 0# define OVERFLOW -2typedef int Status,KeyType;struct RedTypeKeyType key;/关键字项;/记录类型struct SqListRedType *r;/r0闲置或用作哨兵单元int length;/顺序表长度;/顺序表类型/Status CreateList(SqList &L,int num)L.r=(RedType *)malloc(sizeof(RedType)*(num+1);if(!L.r)exit(OVERFLOW);L.length=num;return OK;KeyType ValueList(SqList &L,int num,KeyType *m)if(!L.r)return ERROR;int i;for(i=1;i=num;i+)printf(请输入第%d个数：,i);scanf(%d,&L.ri.key);mi=L.ri.key;return *m;Status ReValueList(SqList &L,KeyType *key,int num)if(!L.r)return ERROR;for(int i=1;i=1&change;-i)change=FALSE;for(j=0;jL.rj+1.key)move+,t=L.rj.key,L.rj.key=L.rj+1.key,L.rj+1.key=t,change=TRUE;if(flag)printf(|冒泡排序后顺序表为：),OutputList(L);printf(n|冒泡排序比较次数%d移动次数%dn,count,move);return OK;/Status ShellInsert(SqList &L,int dk,int &count,int &move)int i,j;for(i=dk+1;i=L.length;+i)if(count+,L.ri.key0&(count+,L.r0.keyL.rj.key);j-=dk)move+,L.rj+dk=L.rj;L.rj+dk=L.r0;return OK;Status Shell_Sort(SqList L,int dlta,int num,int flag)int k,count=0,move=0;for(k=0;k希尔排序后顺序表为：),OutputList(L);printf(n|希尔排序比较次数%d移动次数%dn,count,move);return OK;/Status Partition(SqList &L,int low,int high,int &count,int &move)L.r0=L.rlow;KeyType pivotkey;pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;move+,L.rlow=L.rhigh;while(lowhigh&(count+,L.rlow.key=pivotkey)+low;move+,L.rhigh=L.rlow;move+,L.rlow=L.r0;return low;void QSort(SqList &L,int low,int high,int &count,int &move)int pivotloc;if(low快速排序后顺序表为：),OutputList(L);printf(n|快速排序比较次数%d移动次数%dn,count,move);/Status HeapAdjust(SqList &H,int s,int m,int &count,int &move)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，本函数调整H.rs /的关键字，使H.rs.m成为一个大顶堆（对其中记录的关键字而言）RedType rc=H.rs;int j;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选if(jm&(count+,H.rj.key=H.rj.key)break;H.rs=H.rj,move+,s=j;H.rs=rc;return OK;Status HeapSort(SqList &H,int flag)int i,count=0,move=0;RedType t;for(i=H.length/2;i0;-i)HeapAdjust(H,i,H.length,count,move);for(i=H.length;i1;-i)t=H.r1,H.r1=H.ri,H.ri=t;HeapAdjust(H,1,i-1,count,move);if(flag)printf(|堆排序后顺序表为：),OutputList(H);printf(n|堆排序比较次数%d移动次数%dn,count,move);return OK;/Status Merge(RedType SR,RedType TR,int i,int m,int n,int &count,int &move)/将有序的SRi.m和SRm+1.n归并为有序的TRi.nint j,k;for(j=m+1,k=i;i=m&j=n;+k)if(count+,SRi.key=SRj.key)TRk=SRi+,move+;elseTRk=SRj+,move+;while(i=m)TRk+=SRi+,move+;while(j归并排序后顺序表为：),OutputList(L);printf(n|归并排序比较次数%d移动次数%dn,count,move);/Status RandValueList(SqList &L)/用于对顺序表赋1000个随机值if(!L.r)exit(OVERFLOW);int i;srand(time(0);for(i=1;i=1000;i+)L.ri.key=1+(int)(1000.0*rand()/(RAND_MAX+1.0);L.length=1000;return OK;/void main()SqList L;int num,dlta4=5,3,2,1;KeyType key128;printf(请输入待排序数数目：);scanf(%d,&num);CreateList(L,num);/创建表ValueList(L,num,key);/表赋值Bubble_sort(L,1);/冒泡排序ReValueList(L,key,num);/恢复原值Shell_Sort(L,dlta,num,1);/希尔排序ReValueList(L,key,num);/恢复原值QuickSort(L,1);/快速排序ReValueList(L,key,num);/恢复原值HeapSort(L,1);/堆排序ReValueList(L,key,num);/恢复原值MergeSort(L,1);/归并排序CreateList(L,num);/再次创建表以存放随机数RandValueList(L);/产生1000个1到1000之间的随机数Bubble_sort(L,0);/冒泡排序RandValueList(L);/产生1000个1到1000之间的随机数Shell_Sort(L,dlta,num,0);/希尔排序Ran