3-快速排序-实验报告.doc

文档介绍：福建江夏学院《数据结构与关系数据库(本科) 》实验报告姓名班级学号实验日期课程名称数据结构与关系数据库(本科) 指导教师成绩实验名称: 快速排序一、实验目的 1 、掌握快速排序算法; 二、实验环境 1、硬件环境:微机 2、软件环境: Windows XP , 三、实验内容、步骤及结果 1 、实验内容: 对于给定的一组关键字,编写一个快速排序的程序并进行排序输出。 3、代码: #include <> #include <> #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].key<p->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] 将插入有序表*/