C++實(shí)現(xiàn)冒泡排序--希爾排序--快速排序--堆--歸并排序

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;/關(guān)鍵字項(xiàng);/記錄類型struct SqListRedType *r;/r0閑置或用作哨兵單元in

2、t length;/順序表長(zhǎng)度;/順序表類型/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("請(qǐng)輸入第%d個(gè)數(shù)：",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|>>冒泡排序比較次數(shù)%d移動(dòng)次數(shù)%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|>>希爾排序比較次數(shù)%d移動(dòng)次數(shù)%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|>>快速排序比較次數(shù)%d移動(dòng)次數(shù)%dn",count,move);/Status HeapAdjust(SqList &H,int s,int m,int &count,int &move)/已知H.rs.m中記錄的關(guān)鍵字除H.rs.key之外均滿足堆的定義，本函數(shù)調(diào)整H.rs /的關(guān)鍵字，使H.rs.m

10、成為一個(gè)大頂堆（對(duì)其中記錄的關(guān)鍵字而言）RedType rc=H.rs;int j;for(j=2*s;j<=m;j*=2)/沿key較大的孩子結(jié)點(diǎn)向下篩選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|>>堆排序比較次數(shù)%d移動(dòng)次數(shù)%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|>>歸并排序比較次數(shù)%d移動(dòng)次數(shù)%dn",count,move);/Status RandValueList(SqList &L)/用于對(duì)順序表賦1000個(gè)隨機(jī)值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("請(qǐng)輸入待排序數(shù)數(shù)目：");scanf("%d",&num);CreateList(L,num);/創(chuàng)建表ValueList(L,num,key);/表賦值Bubble_sort(L,1);/冒泡排序ReValueList(L,key,num);/恢復(fù)原值Shell_Sort(L,dlta,num,1);/希爾排序ReValueList(L,key,num);/恢復(fù)原值QuickSort(L,1);/快速排序ReValueList(L,key,num);/恢復(fù)原值HeapSort(L,1);/堆排序ReValueList(L,key,num);/恢復(fù)原值MergeSort(L,1);/歸并排序CreateList(L,num);/再次創(chuàng)建表以存放隨機(jī)數(shù)RandValueList(L);/產(chǎn)生1000個(gè)1到1000之間的隨機(jī)數(shù)Bubble_sort(L,