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

《C++实现：冒泡排序--希尔排序--快速排序--堆--归并排序.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include"stdio.h"#include"stdlib.h"#include"time.h"#include"windows.h"#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-2typedefintStatus,KeyType;structRedType{KeyTypekey;//关键字项};//记录类型structSqList{RedType*r;//r[0]闲置或用作哨兵单元intlength;//顺序表长度};//顺序表类型/////

2、///////////////////////////////////////////////////////////////StatusCreateList(SqList&L,intnum){L.r=(RedType*)malloc(sizeof(RedType)*(num+1));if(!L.r)exit(OVERFLOW);L.length=num;returnOK;}KeyTypeValueList(SqList&L,intnum,KeyType*m){if(!L.r)returnERROR;inti;for(i=1;i<

3、=num;i++){printf("请输入第%d个数：",i);scanf("%d",&L.r[i].key);m[i]=L.r[i].key;}return*m;}StatusReValueList(SqList&L,KeyType*key,intnum){if(!L.r)returnERROR;for(inti=1;i<=num;i++)L.r[i].key=key[i];returnOK;}StatusOutputList(SqListL){if(!L.r)returnERROR;intlength=L.length,i;f

4、or(i=1;length;length--,i++)printf("%dt",L.r[i].key);returnOK;}////////////////////////////////////////////////////////////////////StatusBubble_sort(SqListL,intflag){inti,j,change,t,count=0,move=0;for(i=L.length,change=TRUE;i>=1&&change;--i){change=FALSE;for(j=0;j

5、+j)if(count++,L.r[j].key>L.r[j+1].key)move++,t=L.r[j].key,L.r[j].key=L.r[j+1].key,L.r[j+1].key=t,change=TRUE;}if(flag)printf("

6、

7、——>>冒泡排序后顺序表为："),OutputList(L);printf("

8、

9、——>>冒泡排序比较次数%d移动次数%d",count,move);returnOK;}///////////////////////////////////////////////////

10、/////////////////StatusShellInsert(SqList&L,intdk,int&count,int&move){inti,j;for(i=dk+1;i<=L.length;++i)if(count++,L.r[i].key0&&(count++,L.r[0].key

11、hell_Sort(SqListL,intdlta[],intnum,intflag){intk,count=0,move=0;for(k=0;k

12、

13、——>>希尔排序后顺序表为："),OutputList(L);printf("

14、

15、——>>希尔排序比较次数%d移动次数%d",count,move);returnOK;}/////////////////////////////////////////////

16、///////////////////////StatusPartition(SqList&L,intlow,inthigh,int&count,int&move){L.r[0]=L.r[low];KeyTypepivotkey;pivotkey=