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

1、# 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闲置或用作哨兵单元in

2、t 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

3、",&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<=num;i+)L.ri.key=keyi;return OK;Status OutputList(SqList L)if(!L.r)return ERROR;int length=L.length,i;for(i=1;length;length-,i+)printf("%dt",L.ri.key);ret

4、urn OK;/Status Bubble_sort(SqList L,int flag)int i,j,change,t,count=0,move=0;for(i=L.length,change=TRUE;i>=1&&change;-i)change=FALSE;for(j=0;j<i;+j)if(count+,L.rj.key>L.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("|>>冒泡排序后顺序表为：&qu

5、ot;),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.key<L.ri-dk.key)L.r0=L.ri;for(j=i-dk;j>0&&(count+,L.r0.key<L.rj.key);j-=d

6、k)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<num;+k)ShellInsert(L,dltak,count,move);if(flag)printf("|>>希尔排序后顺序表为："),OutputList(L);printf("n|>>希尔排序比较次数%d移动次数%dn",count,move);return OK

7、;/Status Partition(SqList &L,int low,int high,int &count,int &move)L.r0=L.rlow;KeyType pivotkey;pivotkey=L.rlow.key;while(low<high)while(low<high&&(count+,L.rhigh.key>=pivotkey)-high;move+,L.rlow=L.rhigh;while(low<high&&(count+,L.rlow.key<=pivotkey)+low;mov

8、e+,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<high)pivotloc=Partition(L,low,high,count,move);QSort(L,low,pivotloc-1,count,move);QSort(L,pivotloc+1,high,count,move);void QuickSort(SqList &L,int flag)int

9、 count=0,move=0;QSort(L,1,L.length,count,move);if(flag)printf("|>>快速排序后顺序表为："),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

10、成为一个大顶堆（对其中记录的关键字而言）RedType rc=H.rs;int j;for(j=2*s;j<=m;j*=2)/沿key较大的孩子结点向下筛选if(j<m&&(count+,H.rj.key<H.rj+1.key)+j;if(count+,rc.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;i>

11、0;-i)HeapAdjust(H,i,H.length,count,move);for(i=H.length;i>1;-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,in

12、t 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<=n)TRk+=SRj+,move+;return OK;Status Msort(RedType SR,RedType TR1,int s,int t,int &a

13、mp;count,int &move)int m;RedTypeTR21001;if(s=t)TR1s=SRs;elsem=(s+t)/2;Msort(SR,TR2,s,m,count,move);Msort(SR,TR2,m+1,t,count,move);Merge(TR2,TR1,s,m,t,count,move);return OK;void MergeSort(SqList &L,int flag)int count=0,move=0;Msort(L.r,L.r,1,L.length,count,move);if(flag)printf("|>>

14、归并排序后顺序表为："),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;i

15、nt 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,