数据结构 课程设计-排序算法实现.doc

河南工程学院数据结构与算法课程设计成果报告排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计思路12 分析与设计22.1 题目需求分析22.2 算法描述22.3 程序流程图83 程序清单94 测试154.1 测试结果分析155 总结18参考文献191 课程设计目标与任务1.1 课程设计目标（1）了解并掌握数据结构与算法的设计方法，培养独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法，独立分析和解决问题的能力，增强理论与实践相结合的技巧；（4）学会自己查阅资料，提高自学能力，努力做到有问题尽量自己解决，并能在同学交流之间增强团队意识；（5）训练用系统的观点和软件开发一般规范进行软件开发；（6）了解并掌握程序的运行调试、排除错误的常用技巧。1.2 课程设计任务 设计排序相关函数库，以便在程序设计中调用，要求设计程序，产生20000个随机数，完成下面功能：（1）对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序，并把排序结果进行保存。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计思路根据直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序等排序算法创建出与之对应的函数构成一个函数库，再调用开发环境函数库中的rand()（借用srand()函数设置时间种子）函数生成调试程序所需的随机数，同时储存到一个一维数组中。创建main()函数以rand()函数所产生的随机数为实例依次调用排序函数，对排序结果进行分析，结合排序算法以及排序过程对程序运行结果中存在的与实际情况不符合的问题进行分析，通过开发软件进行调试，最终达到问题本身所需要的结果。2 分析与设计2.1 题目需求分析按照题目要求，程序内容应该包括直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序等算法的程序块，即用不同排序方法解决问题所需要的函数，以及随机数生成函数为后续程序运行提供数据，需要创建main()函数对上述系列程序进行调试运行。2.2 算法描述随机数的产生：随机数的产生利用srand()函数设置随机数种子，作为伪随机数计算的依据，利用rand()函数生成随机数并将其循环储存到一维数组中。#include #include #include using namespace std;int main(void) int a100=0; int i; srand(unsigned int)time(NULL);/设置随机数种子 for(i=0;i100;i+) ai=rand() % 100 ; /生成随机数并储存 for(i=0;i100;i+) printf( %d,ai); return 0;直接插入排序：是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。void InsertSort(RecType R,int n) /*直接插入排序*/int i,j,k;RecType temp;for (i=1;i=0 & temp.keyRj.key) Rj+1=Rj;/*将关键字大于Ri.key的记录后移*/j-; Rj+1=temp; 折半插入排序：它的基本思想是在插入排序的基础之上采用二分法缩小比较范围，很大程度的节省了程序运行时间。void BInsertSort(RecType R,int n)/*折半直接插入排序*/int i,j,k;for(i=2; i=n; +i) R0 = Ri;int low=1,high=i-1;while(low=high) int m=(low+high)/2;if(R0.key=high+1; j-)Rj+1=Rj; Rhigh+1=R0;希尔排序：“缩小增量排序”，它也是一种属插入排序类的方法，它的基本思路是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。void ShellSort(RecType R,int n)/*希尔排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;冒泡排序：它的过程很简单，首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个和第三个记录的关键字，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。void BubbleSort(RecType R,int n)/*冒泡排序算法*/int i,j,k;RecType temp;for (i=0;ii;j-) /*比较,找出本趟最小关键字的记录*/if (Rj.keyRj-1.key) temp=Rj; /*将最小关键字记录前移*/Rj=Rj-1;Rj-1=temp;快速排序：它是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，已达到整个序列有序。void QuickSort(RecType R,int s,int t) /*对Rs至Rt的元素进行快速排序*/int i=s,j=t,k;RecType temp;if (si & Rj.keytemp.key) j-;/*从右向左扫描,找第1个关键字小于temp.key的Rj */ if (ij) /*表示找到这样的Rj,Ri、Rj交换*/Ri=Rj;i+; while (ij & Ri.keytemp.key) i+;/*从左向右扫描,找第1个关键字大于temp.key的记录Ri */ if (ij) /*表示找到这样的Ri,Ri、Rj交换*/Rj=Ri;j-; Ri=temp;QuickSort(R,s,i-1); /*对左区间递归排序*/QuickSort(R,i+1,t); /*对右区间递归排序*/简单选择排序：它的基本思路是通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1=i=n）个记录交换之。void SelectSort(RecType R,int n)/*简单选择排序算法*/int i,j,k,l;RecType temp;for (i=0;in-1;i+) /*做第i趟排序*/k=i;for (j=i+1;jn;j+) /*在当前无序区Ri.n-1中选key最小的Rk */if (Rj.keyRk.key)k=j; /*k记下目前找到的最小关键字所在的位置*/if (k!=i) /*交换Ri和Rk */temp=Ri;Ri=Rk;Rk=temp;堆排序：它首先需要一个记录大小的辅助空间，且每个带排序的记录仅占有一个存储空间。void DispHeap(RecType R,int i,int n)/*以括号表示法输出建立的堆*/if (i=n)printf(%d,Ri.key);/*输出根结点*/if (2*i=n | 2*i+1n)printf();if (2*i=n)DispHeap(R,2*i,n);/*递归调用输出左子树*/printf(,);if (2*i+1=n)DispHeap(R,2*i+1,n);/*递归调用输出右子树*/printf();void Sift(RecType R,int low,int high) /*调整堆*/int i=low,j=2*i; /*Rj是Ri的左孩子*/RecType temp=Ri;while (j=high)if (jhigh & Rj.keyRj+1.key) /*若右孩子较大,把j指向右孩子*/j+; /*变为2i+1*/ if (temp.key=1;i-) /*循环建立初始堆*/Sift(R,i,n);printf( 初始堆:);DispHeap(R,1,n);printf(n);/*输出初始堆*/for (i=n;i=2;i-) /*进行n-1次循环,完成推排序*/printf( 交换%d与%d,输出%dn,Ri.key,R1.key,R1.key);temp=R1; /*将第一个元素同当前区间内R1对换*/ R1=Ri; Ri=temp; Sift(R,1,i-1); /*筛选R1结点,得到i-1个结点的堆*/printf( 筛选调整得到堆:);DispHeap(R,1,i-1);printf(n);/*输出每一趟的排序结果*/2-路归并排序：它的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。void Merge(RecType R,int low,int mid,int high) /*将两个有序表Rlow.mid和Rmid+1.high归并为一个有序表Rlow.high中*/RecType *R1;int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /*动态分配空间*/while (i=mid & j=high) /*在第1段和第2段均未扫描完时循环*/if (Ri.key=Rj.key) /*将第1段中的记录放入R1中*/R1k=Ri;i+;k+; else /*将第2段中的记录放入R1中*/R1k=Rj;j+;k+; while (i=mid) /*将第1段余下部分复制到R1*/R1k=Ri;i+;k+; while (j=high) /*将第2段余下部分复制到R1*/R1k=Rj;j+;k+; for (k=0,i=low;i=high;k+,i+) /*将R1复制回R中*/ Ri=R1k;void MergePass(RecType R,int length,int n)/*实现一趟归并*/int i;for (i=0;i+2*length-1n;i=i+2*length) /*归并length长的两相邻子表*/Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n) /*余下两个子表,后者长度小于length*/Merge(R,i,i+length-1,n-1); /*归并这两个子表*/void MergeSort(RecType R,int n) /*二路归并排序算法*/int length,k,i=1;/*i用于累计归并的趟数*/for (length=1;lengthn;length=2*length)MergePass(R,length,n);从第一个元素开始直到结束开始（main）2.3 程序流程图low!=hight mid=(low+hight)/2.R0.key0排序增量小于元素个数ShellSort保存待插入元素查找插入位置BubbleSort记录后移插入记录QuickSort是否是否需要排序SelectSort向 左 查 找排序码小于temp寻找temp的最终位置HeapSort移动元素向 右 查 找排序码大于tempMergeSort移动元素结束递归处理左区间递归处理右区间图（2.1程序流程）3 程序清单#include #include #include #include #define MaxSize 20000typedef int KeyType;typedef char InfoType10;typedef struct KeyType key; InfoType data;RecType;void InsertSort(RecType R,int n) ;/*对R0.n-1按递增有序进行直接插入排序*/void BInsertSort(RecType R,int n);/*对R0.n-1按递增有序进行折半直接插入排序*/void ShellSort(RecType R,int n); /*希尔排序算法*/void BubbleSort(RecType R,int n); /*冒泡排序算法*/void QuickSort(RecType R,int s,int t); /*对Rs至Rt的元素进行快速排序*/void SelectSort(RecType R,int n); /*直接选择排序算法*/void DispHeap(RecType R,int i,int n);/*以括号表示法输出建立的堆*/void Sift(RecType R,int low,int high);/*调整堆*/void HeapSort(RecType R,int n);/*对R1到Rn元素实现堆排序*/void Merge(RecType R,int low,int mid,int high); /*将两个有序表Rlow.mid和Rmid+1.high归并为一个有序表Rlow.high中*/void MergePass(RecType R,int length,int n); /*实现一趟归并*/void MergeSort(RecType R,int n); /*二路归并排序算法*/int main() int i,j,k,n=10; KeyType aMaxSize=0; RecType RMaxSize; srand(unsigned int)time(NULL); /用于初始化数据种子 for(i=0;in;i+) ai=rand()%20000; /将随机数储存到数字中 printf(实验数据：n); for(i=0;in;i+) printf(%6d,ai); printf(n); for(i=0;in;i+) Ri.key=ai; printf(直接插入排序过程及结果：n); InsertSort(R,n); for(i=0;in;i+) Ri+1.key=ai; printf(折半插入排序过程及结果：n); BInsertSort(R,n); for(i=0;in;i+) Ri.key=ai; printf(希尔排序过程及结果：n); ShellSort(R,n); for(i=0;in;i+) Ri.key=ai; printf(冒泡排序过程及结果：n); BubbleSort(R,n); for(i=0;in;i+) Ri.key=ai; printf(快速排序过程及结果：n); QuickSort(R,0,n-1); for(i=0;in;i+) Ri.key=ai; printf(直接选择排序过程及结果：n); SelectSort(R,n); for(i=0;in;i+) Ri.key=ai; printf(堆排序过程及结果：n); HeapSort(R,n); for(i=0;in;i+) Ri.key=ai; printf(2-归并排序过程及结果：n); MergeSort(R,n); return 0;void InsertSort(RecType R,int n) /*直接插入排序*/int i,j,k;RecType temp;for (i=1;i=0 & temp.keyRj.key)Rj+1=Rj;/*将关键字大于Ri.key的记录后移*/j-; Rj+1=temp;/*在j+1处插入Ri*/printf( i=%d ,i);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%6d,Rk.key);printf(n);void BInsertSort(RecType R,int n)/*折半直接插入排序*/int i,j,k;for(i=2; i=n; +i) R0 = Ri;int low=1,high=i-1;while(low=high) int m=(low+high)/2;if(R0.key=high+1; j-)Rj+1=Rj; Rhigh+1=R0; printf( i=%d ,i-1);/*输出每一趟的排序结果*/for (k=1; k0)for (i=d;i=0 & Rj.keyRj+d.key)temp=Rj; /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%6d,Rk.key);printf(n); d=d/2; /*递减增量d*/void BubbleSort(RecType R,int n)/*冒泡排序*/int i,j,k;RecType temp;for (i=0;ii;j-)/*比较,找出本趟最小关键字的记录*/if (Rj.keyRj-1.key)temp=Rj; /*Rj与Rj-1进行交换,将最小关键字记录前移*/Rj=Rj-1;Rj-1=temp;printf( i=%d ,i);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%6d,Rk.key);printf(n);void QuickSort(RecType R,int s,int t) /*快速排序*/int i=s,j=t,k;RecType temp;if (si & Rj.keytemp.key) j-; /*从右向左扫描,找第1个关键字小于temp.key的Rj */ if (ij) /*表示找到这样的Rj,Ri、Rj交换*/Ri=Rj;i+; while (ij & Ri.keytemp.key) i+;/*从左向右扫描,找第1个关键字大于temp.key的记录Ri */ if (ij) /*表示找到这样的Ri,Ri、Rj交换*/Rj=Ri;j-; Ri=temp;printf( );/*输出每一趟的排序结果*/for (k=0;k10;k+)if (k=i)printf( %d,Rk.key);elseprintf(%6d,Rk.key);printf(n);QuickSort(R,s,i-1); /*对左区间递归排序*/QuickSort(R,i+1,t); /*对右区间递归排序*/void SelectSort(RecType R,int n)/*直接选择排序*/int i,j,k,l;RecType temp;for (i=0;in-1;i+) /*做第i趟排序*/k=i;for (j=i+1;jn;j+) /*在当前无序区Ri.n-1中选key最小的Rk */if (Rj.keyRk.key)k=j; /*k记下目前找到的最小关键字所在的位置*/if (k!=i) /*交换Ri和Rk */temp=Ri;Ri=Rk;Rk=temp;printf( i=%d ,i);/*输出每一趟的排序结果*/for (l=0;ln;l+)printf(%6d,Rl.key);printf(n);void DispHeap(RecType R,int i,int n)/*以括号表示法输出建立的堆*/if (i=n)printf( %d,Ri.key);/*输出根结点*/if (2*i=n | 2*i+1n)printf( ();if (2*i=n)DispHeap(R,2*i,n); /*递归调用输出左子树*/printf(,);if (2*i+1=n)DispHeap(R,2*i+1,n); /*递归调用输出右子树*/printf() );void Sift(RecType R,int low,int high) /*调整堆*/int i=low,j=2*i; /*Rj是Ri的左孩子*/RecType temp=Ri;while (j=high)if (jhigh & Rj.keyRj+1.key) /*若右孩子较大,把j指向右孩子*/j+; /*变为2i+1*/ if (temp.key=1;i-) /*循环建立初始堆*/Sift(R,i,n);printf( 初始堆:);DispHeap(R,1,n);printf(n);/*输出初始堆*/for (i=n;i=2;i-) /*进行n-1次循环,完成推排序*/printf( 交换%d与%d,输出%dn,Ri.key,R1.key,R1.key);temp=R1; /*将第一个元素同当前区间内R1对换*/ R1=Ri; Ri=temp; Sift(R,1,i-1); /*筛选R1结点,得到i-1个结点的堆*/printf( 筛选调整得到堆:);DispHeap(R,1,i-1);printf(n);/*输出每一趟的排序结果*/void Merge(RecType R,int low,int mid,int high) /*2路归并排序 */RecType *R1;int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /*动态分配空间*/while (i=mid & j=high) /*在第1段和第2段均未扫描完时循环*/if (Ri.key=Rj.key) /*将第1段中的记录放入R1中*/R1k=Ri;i+;k+; else /*将第2段中的记录放入R1中*/R1k=Rj;j+;k+; while (i=mid) /*将第1段余下部分复制到R1*/R1k=Ri;i+;k+; while (j=high) /*将第2段余下部分复制到R1*/R1k=Rj;j+;k+; for (k=0,i=low;i=high;k+,i+) /*将R1复制回R中*/ Ri=R1k;void MergePass(RecType R,int length,int n)/*实现一趟归并*/int i;for (i=0;i+2*length-1n;i=i+2*length) /*归并length长的两相邻子表*/Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n) /*余下两个子表,后者长度小于length*/Merge(R,i,i+length-1,n-1); /*归并这两个子表*/void MergeSort(RecType R,int n) /*二路归并排序*/int length,k,i=1;/*i用于累计归并的趟数*/for (length=1;lengthn;length=2*length)MergePass(R,length,n);printf( 第%d趟归并 ,i+);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%6d,Rk.key);printf(n);4 测试4.1 测试结果分析便与程序的顺利，此次结果选用10个数据进行程序的调试与运行。 图（4.1）直接插入、折半插入排序结果图（4.2）希尔、冒泡排序结果图（4.3）快速、直接选择排序结果图（4.4）堆排序结果图（4.5）归并排序结果以上排序结果与设计初期预想结果基本相同，以上排序方法的排序过程很好的说明了各种排序算法的思想。其中直接插入排序算法体现了以第一个纪录为关键字，依次将第1n-1个纪录进行比较插入直至序列有序；这般插入排序是在插入排序的基础之上采用二分缩小比较范围，很大程度上缩减了程序运行时间；希尔排序采用“缩小增量法”将序列分成整体有序块，再在每个分段内部进行插入排序，将程序运行时间再次缩短；冒泡排序基本思想很简单，就是将相邻的纪录进行比较并按照规定判断是否进行交换直至序列有序；快速排序是在冒泡排序的基础之上引用二分法，将序列分成两个部分线性缩短程序运行时间；选择排序的基本思想就是通过比较选择出序列中最小或最大的纪录，将他们置于序列头或序列尾，依次操作直至序列有序；堆排序就是借用辅助空间（如二叉树）按照一定的规则储存数据，然后再对辅助工具进行相关操作直至序列有序；归并排序基本是象就是通过依次比较、依次插入对两个有序序列进行合并，得到一个有序序列。5 总结通过一个星期的忙碌，最终换来了程序设计实训的圆满结束。有了上学期实训的经验，在本次实训开始根据老师提供的题目，结合本学期所学习的数据结构知识及自身情况，最终我选择了随机数的生成及排序的实现来完成我的数据结构程序设计实训。在实训中我根据本学期所学算法结合我的C与语言基础将直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序等排序算法代码化，在后期调试运行的过程中根据结果多次对每一个函数进行优化，并且通过查阅资料了解并掌握了随机数生成中srand()函数与rand()函数的运行机制与方法，最后通过main()将所有函数整合到一起并调试运行很成功，成功解决老师所提供的问题。参考文献1严蔚敏.数据结构（C语言版）.清华大学出版社2谭浩强.C程序设计（第四版）.清华大学出版社3谭浩强.C+面向对象程序对象设计.清华大学出版社4刘汝佳.算法竞赛入门经典.清华大学出版社5刘汝佳.算法艺术与信息学竞赛.清华大学出版社 #include #include #include #include #define MaxSize 20000typedef int KeyType;typedef char InfoType10;typedef struct KeyType key; InfoType data;RecType;void InsertSort(RecType R,int n) ;/*对R0.n-1按递增有序进行直接插入排序*/void BInsertSort(RecType R,int n);/*对R0.n-1按递增有序进行折半直接插入排序*/void ShellSort(RecType R,int n); /*希尔排序算法*/void BubbleSort(RecType R,int n); /*冒泡排序算法*/void QuickSort(RecType R,int s,int t); /*对Rs至Rt的元素进行快速排序*/void SelectSort(RecType R,int n); /*直接选择排序算法*/void DispHeap(RecType R,int i,int n);/*以括号表示法输出建立的堆*/void Sift(RecType R,int low,int high);/*调整堆*/void HeapSort(RecType R,int n);/*对R1到Rn元素实现堆排序*/void Merge(RecType R,int low,int mid,int high); /*将两个有序表Rlow.mid和Rmid+1.high归并为一个有序表Rlow.high中*/void MergePass(RecType R,int length,i