《快速排序-实验报告》由会员分享，可在线阅读，更多相关《快速排序-实验报告（5页珍藏版）》请在装配图网上搜索。
1、福建江夏学院数据结构与关系数据库（本科）实验报告姓名 班级 学号 实验日期 课程名称 数据结构与关系数据库（本科） 指导教师 成绩实验名称：快速排序一、 实验目的1、掌握快速排序算法；二、 实验环境1、 硬件环境：微机2、 软件环境： Windows XP，VC6.0三、实验内容、步骤及结果1、实验内容：对于给定的一组关键字，编写一个快速排序的程序并进行排序输出。3、 代码：#include #include #define MAXSIZE 1000typedef int KeyType;typedef struct KeyType key;/* 关键码字段，可以是整型、字符串型、构造类型等*
2、/ElemType;ElemType rMAXSIZE;/* 顺序存储结构*/typedef struct ElemType *r;/* 数组基址*/ int length;/* 表长度*/S_TBL;void CreateTestData(S_TBL * tbl) tbl-r=r; tbl-r0.key=0;/辅助单元，默认存放0 tbl-r1.key=503; tbl-r2.key=87; tbl-r3.key=512; tbl-r4.key=61; tbl-r5.key=908; tbl-r6.key=170; tbl-r7.key=889; tbl-r8.key=276; tbl-r9
3、.key=675; tbl-r10.key=453; tbl-length=10;void PrintData(S_TBL * tbl) printf(R0:%d R1-%d:,tbl-r0.key,tbl-length);for(int i=1;ilength;i+)printf(%03d ,tbl-ri.key);printf(n);/*直接插入排序*/void InsertSort(S_TBL * p)int i,j;for(i=2;ilength;i+)if(p-ri.key ri-1.key) /*小于时，需将elemi插入有序表*/ p-r0.key=p-ri.key; /*为统一
4、算法设置监测*/ for(j=i-1;p-r0.keyrj.key;j-) p-rj+1.key=p-rj.key;/*记录后移*/p-rj+1.key=p-r0.key;/*插入到正确位置*/PrintData(p);/*希尔排序*/void ShellInsert(S_TBL *p,int dk) /*一趟增量为dk 的插入排序，dk 为步长因子*/int i,j; for(i=dk+1;ilength;i+)if(p-ri.key ri-dk.key) /*小于时，需elemi将插入有序表*/ p-r0=p-ri;/*为统一算法设置监测*/ for(j=i-dk;j0 & p-r0.ke
5、yrj.key;j=j-dk) p-rj+dk=p-rj;/*记录后移*/p-rj+dk=p-r0;/*插入到正确位置*/void ShellSort(S_TBL *p,int dlta,int t) /*按增量序列dlta0，1，t-1对顺序表*p 作希尔排序*/ for(int k=0;klength;for(i=1;i=i;j-)if(p-rj.keyp-rj+1.key)swap=p-rj;p-rj=p-rj+1;p-rj+1=swap;noswap=0;PrintData(p);/*简单选择排序*/void SelectSort(S_TBL *s) int i,j,t;ElemTyp
6、e swap;for(i=1;ilength;i+) /* 作length-1 趟选取*/for(j=i+1,t=i;jlength;j+) /* 在i 开始的length-n+1 个记录中选关键码最小的记录*/if(s-rt.keys-rj.key)t=j;/* t 中存放关键码最小记录的下标*/swap=s-rt;/* 关键码最小的记录与第i 个记录交换*/ s-rt=s-ri;s-ri=swap;PrintData(s);int Partition(S_TBL *tbl,int low,int high) /*一趟快排序*/ /*交换顺序表tbl 中子表tbl-lowhigh的记录，使支
7、点记录到位，并反回其所在位置*/ /*此时，在它之前(后)的记录均不大(小)于它*/int pivotkey;tbl-r0=tbl-rlow; /*以子表的第一个记录作为支点记录*/pivotkey=tbl-rlow.key; /*取支点记录关键码*/while(lowhigh) /*从表的两端交替地向中间扫描*/ while(lowrhigh.key=pivotkey) high-;tbl-rlow=tbl-rhigh; /*将比支点记录小的交换到低端*/PrintData(tbl);while(lowrlow.keyrhigh=tbl-rlow; /*将比支点记录大的交换到低端*/Prin
8、tData(tbl);tbl-rlow=tbl-r0; /*支点记录到位*/PrintData(tbl);return low; /*反回支点记录所在位置*/void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/ /*对顺序表tbl 中的子序列tbl-lowhigh作快排序*/int pivotloc;if(lowhigh) pivotloc=Partition(tbl,low,high); /*将表一分为二*/PrintData(tbl);QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/int main(void) S_TBL * tbl=(S_TBL *)malloc(sizeof(S_TBL); CreateTestData(tbl);/InsertSort(tbl);/int dlta3=5,3,1; /ShellSort(tbl,dlta,3);/BubbleSort(tbl);/SelectSort(tbl); QSort(tbl,1,10);PrintData(tbl);return 0;3、测试数据与实验结果分析（可以用组合键Alt+Print Screen截图）：四、心得体会
快速排序-实验报告
