数据结构课程设计实验报告(各种排序的实现与效率分析)

1、数据结构课程设计实验报告 实验题目各种排序的实现与效率分析自我评价功 能算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂起泡排序直接排序简单项选择择排序快速排序希尔排序堆排序算法进行比拟比拟结果成绩l A-完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写标准，实验报告表达清晰完整，有详尽的分析和总结。l B-完成实验要求的全部功能，程序代码符合书写标准，实验报告表达清晰完整。l C-完成实验要求的大局部功能，实验报告良好。l D-未按时完成实验，或者抄袭。 教师签名：1、需求分析(1)对起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法

2、进行比拟；(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比拟，比拟指标有：关键字参加比拟次数和关键字的移动次数关键字进行一次交换操作记为3次移动；(3)输出比拟结果。2、主要函数及数据类型函数名功能说明InitData ( )生成随机数组PrintDatat( )输出数组InsertSort ( )直接插入排序ShellInsert ( )对顺序表作一趟希尔插入排序ShellSort ( )希尔排序BubbleSort ( )起泡排序QuickSort ( )快速排序 SelectSort ( )简单项选择择排序 HeapSort ( )堆排序 SortCompare

3、 ( )比拟各种排序方法typedef int KeyType;/定义关键字类型为整数类型typedef int InfoType;/定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean;/* Boolean是布尔类型,其值是TRUE或FALSE */typedef structKeyType key;/关键字项InfoType otherinfo;/其它数据项RedType;/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单

4、元int length;/顺序表长度SqList; /顺序表类型3、源代码/*头文件和宏定义局部*/#include"string.h"#include"ctype.h"#include"time.h"#include"malloc.h" /* malloc()等 */#include"limits.h" /* INT_MAX等 */#include"stdio.h" /* EOF(=Z或F6),NULL */#include"stdlib.h" /* a

5、toi() */#include"io.h" /* eof() */#include"math.h" /* floor(),ceil(),abs() */#include"process.h" /* exit() */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define MAXSIZE 100 /例如数据类型的最大长度typedef int KeyType;/定义关键字类型为整数类型typede

6、f int InfoType;/定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */typedef structKeyType key;/关键字项InfoType otherinfo;/其它数据项RedType;/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型void InitData(SqLis

7、t *L,int dataCopy)int i;L->length=MAXSIZE;srand(unsigned)time(NULL); for(i=0;i<=MAXSIZE;i+)L->ri.otherinfo=0;dataCopyi=L->ri.key=rand();void PrintData(SqList L)int i;for(i=1;i<=L.length;i+)printf("%dt",L.ri.key);void ResumeData(SqList *L,int dataCopy)int i;for(i=0;i<=MAXS

8、IZE;i+)L->ri.key=dataCopyi;void PrintStatistic(int *compareCounts,int *moveCounts)printf("ntt各种排序方法比拟结果:nn");printf("tt起泡排序: 比拟次数 %d,移动次数 %dn",compareCounts0,moveCounts0);printf("tt直接插入排序:比拟次数 %d,移动次数 %dn",compareCounts1,moveCounts1);printf("tt简单项选择择排序:比拟次数 %d,移

9、动次数 %dn",compareCounts2,moveCounts2);printf("tt快速排序: 比拟次数 %d,移动次数 %dn",compareCounts3,moveCounts3);printf("tt希尔排序: 比拟次数 %d,移动次数 %dn",compareCounts4,moveCounts4);printf("tt堆排序: 比拟次数 %d,移动次数 %dn",compareCounts5,moveCounts5);/*直接插入排序*/void InsertSort(SqList *L,int *co

10、mpareCounts,int *moveCounts )/直接插入排序int i,j;/for(i=2;i<=L->length;i+)/从顺序表的第二个元素开始进行比拟if(L->ri.key<L->ri-1.key)/将每个元素与它的前一个元素关键字进行比拟L->r0=L->ri;/如果关键字比前一个元素关键字小，就将元素复制作为哨兵L->ri=L->ri-1;(*moveCounts)+=2;/关键字移动了2次j=i-2;/从要比拟的关键字的前第二个记录开始进行比拟,然后后移while(L->r0.key<L->r

11、j.key)L->rj+1=L->rj;/记录后移(*moveCounts)+;/每作一次后移,移动次数加1j-;(*compareCounts)+;/每作一次比拟，比拟次数加1L->rj+1=L->r0;/插入到正确位置(*compareCounts)+;/*希尔排序*/void ShellInsert(SqList *L,int increment,int *compareCounts,int *moveCounts)/对顺序表作一趟希尔插入排序int j,n;for(j=1+increment;j<=L->length;j+)if(L->rj.k

12、ey<L->rj-increment.key)/将L->i插入到有序增量子表L->r0=L->rj;/暂存在L->r0L->rj=L->rj-increment;(*moveCounts)+=2;for(n=j-2*increment;n>0&&L->r0.key<L->rn.key;n-=increment)L->rn+increment=L->rn;/记录后移，查找插入位置(*moveCounts)+;(*compareCounts)+;L->rn+increment=L->r0

13、;/插入(*moveCounts)+;(*compareCounts)+;void ShellSort(SqList *L,int IncreList,int times,int *compareCounts,int *moveCounts)/希尔排序/按增量序列Increlist0.times-1对顺序表作希尔排序int k;/for(k=0;k<times;k+)ShellInsert(L,IncreListk,compareCounts,moveCounts);/一趟增量为IncreListk的插入排序/*起泡排序*/void BubbleSort(SqList *L,int *c

14、ompareCounts,int *moveCounts)/起泡排序int i,j;for(i=1;i<=L->length;i+)for(j=L->length;j>i;j-)/从后往前两两进行比拟，将元素关键字小的交换到前面if(L->rj.key<L->rj-1.key)L->r0=L->rj;L->rj=L->rj-1;L->rj-1=L->r0;(*moveCounts)+=3;(*compareCounts)+;/*快速排序*/int Partition(SqList *L,int low,int hig

15、h,int *compareCounts,int *moveCounts)/快速排序中的分int pivotkey;L->r0=L->rlow;(*moveCounts)+;pivotkey=L->rlow.key;while(low<high)while(low<high&&L->rhigh.key>=pivotkey)high-;(*compareCounts)+;L->rlow=L->rhigh;(*moveCounts)+;while(low<high&&L->rlow.key<=p

16、ivotkey)low+;(*compareCounts)+;L->rhigh=L->rlow;(*moveCounts)+;(*compareCounts)+;L->rlow=L->r0;(*moveCounts)+;return low;void QSort(SqList *L,int low,int high,int *compareCounts,int *moveCounts)int pivotloc;if(low<high)pivotloc=Partition(L,low,high,compareCounts,moveCounts);QSort(L,lo

17、w,pivotloc-1,compareCounts,moveCounts);QSort(L,pivotloc+1,high,compareCounts,moveCounts);void QuickSort(SqList *L,int *compareCounts,int *moveCounts)QSort(L,1,L->length,compareCounts,moveCounts);/*简单项选择择排序*/void SelectSort(SqList *L,int *compareCounts,int *moveCounts)int i,j,minPoint;for(i=1;i<

18、;=L->length;i+)L->r0=L->ri;(*moveCounts)+;minPoint=i;for(j=i+1;j<=L->length;j+)if(L->rj.key<L->r0.key)L->r0=L->rj;(*moveCounts)+;minPoint=j;(*compareCounts)+;L->rminPoint=L->ri;L->ri=L->r0;(*moveCounts)+;/*堆排序*/void HeapAdjust(SqList *L,int s,int m,int *comp

19、areCounts,int *moveCounts)RedType cmpKey;/待比拟的值int j;cmpKey=L->rs;(*moveCounts)+;for(j=s*2;j<=m;j*=2)(*compareCounts)+=2;if(j<m&&L->rj.key<L->rj+1.key) j+;if(!(cmpKey.key<L->rj.key) break;L->rs=L->rj;(*moveCounts)+;s=j;L->rs=cmpKey;(*moveCounts)+;void HeapSor

20、t(SqList *L,int *compareCounts,int *moveCounts)int i;RedType temp;for(i=L->length/2;i>0;i-)HeapAdjust(L,i,L->length,compareCounts,moveCounts);for(i=L->length;i>1;i-)temp=L->r1;L->r1=L->ri;L->ri=temp;(*moveCounts)+=3;HeapAdjust(L,1,i-1,compareCounts,moveCounts);void SortCom

21、pare()SqList L;/用顺序表存放待排序的元素int dataCopyMAXSIZE+1,i;int compareCounts7,moveCounts7;int increList6;for(i=0;i<5;i+)increListi=(int)pow(2,7-i)-1;increList5=1;for(i=0;i<7;i+)compareCountsi=0;moveCountsi=0;InitData(&L,dataCopy);/初始化数据，随机产生100个正整数的数列printf("ttt初始化数据后产生的数列:n");PrintData

22、(L);/显示出未排序的数列printf("nnttt经过起泡排序后产生的数列:n");BubbleSort(&L,&compareCounts0,&moveCounts0);/对数列使用起泡排序PrintData(L);/显示出排序好的数列ResumeData(&L,dataCopy);printf("nnttt经过直接插入排序后产生的数列:n");InsertSort(&L,&compareCounts1,&moveCounts1);/对数列使用插入排序PrintData(L);/显示出排序好的数列ResumeData(&L,dataCopy);printf("nnttt经过简单项选择择排序后产生的数列:n&