快速排序-实验报告

《快速排序-实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、福建江夏学院《数据结构与关系数据库（本科）》实验报告姓名班级学号实验日期课程名称数据结构与关系数据库（本科）指导教师成绩实验名称：快速排序一、实验目的1、掌握快速排序算法；二、实验环境1、硬件环境：微机2、软件环境：WindowsXP，VC6.0三、实验内容、步骤及结果1、实验内容：对于给定的一组关键字，编写一个快速排序的程序并进行排序输出。3、代码：#include#include#defineMAXSIZE1000typedefintKeyType;typedefstruct{K

2、eyTypekey;/*关键码字段，可以是整型、字符串型、构造类型等*/}ElemType;ElemTyper[MAXSIZE];/*顺序存储结构*/typedefstruct{ElemType*r;/*数组基址*/intlength;/*表长度*/}S_TBL;voidCreateTestData(S_TBL*tbl){tbl->r=r;tbl->r[0].key=0;//辅助单元，默认存放0tbl->r[1].key=503;tbl->r[2].key=87;tbl->r[3].key=512;tbl->r[4].k

3、ey=61;tbl->r[5].key=908;tbl->r[6].key=170;第5页共5页tbl->r[7].key=889;tbl->r[8].key=276;tbl->r[9].key=675;tbl->r[10].key=453;tbl->length=10;}voidPrintData(S_TBL*tbl){printf("R[0]:%dR[1-%d]:",tbl->r[0].key,tbl->length);for(inti=1;i<=tbl->length;i++){printf("%03d",tbl-

4、>r[i].key);}printf("");}/*直接插入排序*/voidInsertSort(S_TBL*p){inti,j;for(i=2;i<=p->length;i++){if(p->r[i].keyr[i-1].key)/*小于时，需将elem[i]插入有序表*/{p->r[0].key=p->r[i].key;/*为统一算法设置监测*/for(j=i-1;p->r[0].keyr[j].key;j--){p->r[j+1].key=p->r[j].key;/*记录后移*/}p->r[j+

5、1].key=p->r[0].key;/*插入到正确位置*/}//PrintData(p);}}/*希尔排序*/voidShellInsert(S_TBL*p,intdk){/*一趟增量为dk的插入排序，dk为步长因子*/inti,j;for(i=dk+1;i<=p->length;i++){if(p->r[i].keyr[i-dk].key)/*小于时，需elem[i]将插入有序表*/{p->r[0]=p->r[i];/*为统一算法设置监测*/for(j=i-dk;j>0&&p->r[0].keyr[j

6、].key;j=j-dk){p->r[j+dk]=p->r[j];/*记录后移*/第5页共5页}p->r[j+dk]=p->r[0];/*插入到正确位置*/}}}voidShellSort(S_TBL*p,intdlta[],intt){/*按增量序列dlta[0，1…，t-1]对顺序表*p作希尔排序*/for(intk=0;k

7、p){inti,j,n,noswap=0;ElemTypeswap;n=p->length;for(i=1;i<=n-1&&!noswap;i++){noswap=1;for(j=n-1;j>=i;j--){if(p->r[j].key>p->r[j+1].key){swap=p->r[j];p->r[j]=p->r[j+1];p->r[j+1]=swap;noswap=0;}}PrintData(p);}}/*简单选择排序*/voidSelectSort(S_TBL*s){inti,j,t;ElemTypeswap;f

8、or(i=1;ilength;i++){/*作length-1趟选取*/for(j=i+1,t=i;j<=s->length;j++){/*在i开始的length-n+1个记录中选关键码最小的记录*/if(s->r[t].key>s->r[j].key)第5页共5页t=j;/*t中存放关键码最小记录的下标*/