快速排序试验报告.doc

福建江夏学院 《数据结构与关系数据库（本科）》实验报告 姓名 班级 学号 实验日期 课程名称 数据结构与关系数据库（本科） 指导教师 成绩 实验名称：快速排序 实验目的 1、掌握快速排序算法； 实验环境 硬件环境：微机 软件环境： Windows XP，VC6.0 三、实验内容、步骤及结果 1、实验内容： 对于给定的一组关键字，编写一个快速排序的程序并进行排序输出。 代码： #include stdio.h #include stdlib.h #define MAXSIZE 1000 typedef int KeyType; typedef struct{ KeyType key;/* 关键码字段，可以是整型、字符串型、构造类型等*/ }ElemType; ElemType r[MAXSIZE]; /* 顺序存储结构*/ typedef struct{ ElemType *r;/* 数组基址*/ int length;/* 表长度*/ }S_TBL; void CreateTestData(S_TBL * tbl) { tbl-r=r; tbl-r[0].key=0;//辅助单元，默认存放0 tbl-r[1].key=503; tbl-r[2].key=87; tbl-r[3].key=512; tbl-r[4].key=61; tbl-r[5].key=908; tbl-r[6].key=170; tbl-r[7].key=889; tbl-r[8].key=276; tbl-r[9].key=675; tbl-r[10].key=453; tbl-length=10; } void PrintData(S_TBL * tbl) { printf(R[0]:%d R[1-%d]:,tbl-r[0].key,tbl-length); for(int i=1;i=tbl-length;i++) { printf(%03d ,tbl-r[i].key); } printf(\n); } /*直接插入排序*/ void InsertSort(S_TBL * p) { int i,j; for(i=2;i=p-length;i++) { if(p-r[i].key p-r[i-1].key) /*小于时，需将elem[i]插入有序表*/ { p-r[0].key=p-r[i].key; /*为统一算法设置监测*/ for(j=i-1;p-r[0].keyp-r[j].key;j--) { p-r[j+1].key=p-r[j].key;/*记录后移*/ } p-r[j+1].key=p-r[0].key;/*插入到正确位置*/ } //PrintData(p); } } /*希尔排序*/ void ShellInsert(S_TBL *p,int dk) { /*一趟增量为dk 的插入排序，dk 为步长因子*/ int i,j; for(i=dk+1;i=p-length;i++) { if(p-r[i].key p-r[i-dk].key) /*小于时，需elem[i]将插入有序表*/ { p-r[0]=p-r[i];/*为统一算法设置监测*/ for(j=i-dk;j0 p-r[0].keyp-r[j].key;j=j-dk) { p-r[j+dk]=p-r[j];/*记录后移*/ } p-r[j+dk]=p-r[0];/*插入到正确位置*/ } } } void ShellSort(S_TBL *p,int dlta[],int t) { /*按增量序列dlta[0，1…，t-1]对顺序表*p 作希尔排序*/ for(int k=0;kt;k++) { ShellInsert(p,dlta[k]);/*一趟增量为dlta[k]的插入排序*/ //PrintData(p); } } /*冒泡排序*/ void BubbleSort(S_TBL *p) { int i,j,n,noswap=0; ElemType swap; n=p-length; for(i=1;i=n-1 !noswap;i++) { noswap=1; for(j=n-1;j=i;j--) { i