《王帅-E11314150-排序算法》由会员分享，可在线阅读，更多相关《王帅-E11314150-排序算法（29页珍藏版）》请在金锄头文库上搜索。
1、 课程设计报告课程名称: 数据结构 课程设计课程设计题目:排序算法姓 名: *院系: 计算机学院 专 业:计算机科学与技术 年 级:2013 级 学 号:*指导教师:* 2015 年 *月 * 日 (1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2 需求分析随机产生 1000000 数值在 029999 个数，并用四种不同的方法进行排序，将结果在文件中显示出来，并比较四种排
2、序的区别，分析各自的特点。3 课程设计报告内容 3.1 概要设计此次题目分为 4 部分，要用 4 中不同的排序方法进行排序，并对这 4 中排序进行比较。（1） 插入排序：插入排序的基本思想就是对于新输入的数，与前面已存在的数组中的数进行比较，选择合适的位置将其插入其中。设计关键字 key 用来存放每次读取的数，在数组的范围内，从后往前依次与数组中的值进行比较，直到找到不比 key 大的数，那些比 key 大的数则依次往后进行移位。如此就可以完成一个数的插入，对于每一个数执行上述操作就可得到排序好的数组。（2） 堆排序：堆排序的基本思想就是对于要进行排序的数，建立最大堆，根据最大堆的特性（根结点
3、的值不小于左右子结点的值）由此从上到下使得整个要进行排序的数组基本有序，然后在此基础上将最大的依次提取出来，从数组末尾开始，依次往前排。最终就得到完全有序的的数组，即完成排序。（3） 快速排序：运用分治法来具体地实现快速排序，对于程序中的待排序的元素，将最后一个元素设为 key 与所有元素进行比较，若发现比 key 大则继续往后进行比较，若发现比key 小，则将较小元素和第一个不比 key 小的元素交换位置，这样依次执行，到最后交换 key 和第一个不比 key 小的元素的位置，此时，key 左边的元素全部小于key，右边的全部不小于 key，这就相当于已经将 key 的位置找到了，然后对 k
4、ey左右两侧的子数组重复上述操作，直到排好所有的元素。则排序就完成。（4） 计数排序：计数排序的思想很简单，即就是开辟很大的数组，在以元素的值为数组下标的位置进行计数，看原来的数组中此元素值的数有几个，然后用数组前一个元素的值与当前位置元素相加，处理元素在将要排好序的新数组中的位置，然后从后往前，将原数组的值放到相应的新的数组对应的位置上。3.2 详细设计 为了可以进行对比，在以下 4 种排序算法的设计过程中，都要输出两次，一次是随机产生的未进行排序的数，将其输出到”test1.txt”中，然后将排序之后的有序数组中的元素按顺序输出到 ”test2.txt”中。此处的输出到 txt 文档均采用
5、 fprintf 函数，随机产生的1000000 个数均采用 rand()函数，算法的计时均采用 clock()函数。（1）插入排序：插入排序算法的主要步骤就是进行比较并插入，从数组中的第二个元素开始，首先将此元素值付给关键字 key，然后用 key 与数组前面的元素进行比较，若是前面的元素大于关键字，就将前面的元素后移一位，在数组范围内，直到找到某个元素不大于关键字，就将关键字插入到此元素后面，如此反复进行操作，就可以将原数组中的元素全部排序（2）堆排序： 由于堆排序中要用到根节点的左右子树来进行比较排序，由于 L=2*i,R=2*i+1 因此要从数组的第 1 号单元开始进行比较，所以开始时
6、开辟 N+1 个空间进行排序。用函数MAX_PEAPIFY(int *A,int i)来判断 A 数组中的 i 结点是否满足 i 结点不小于它的左右结点，若不满足，则进行替换，将三个数中最大的一个替换到根节点上，如此对所有结点执行此操作，可得基本有序的数组。此时最大值在数组的开头，然后将最大的与数组最末尾的值进行替换，此时最大数排到了数组的末尾，在调用 MAX_PEAPIFY(int *A,int i)函数对前面的结点依次进行检查整理。这时除了最后结点之外的最大结点就到了数组开始位置，在于数组中倒数第二位置的元素进行替换，就这样依次执行，最终可得到从后往前依次递减的有序数组，即完成排序。（3）
7、快速排序：首先要设置两个位置的标记 i 和 j，i 数组第一个元素之前，每次比较，发现比 key 小的值，就将 i+1，用 j 定位目前比较的位置，从左往右依次进行比较，若发现比 key 小的值，用 i 和 j 的标记将此值与第一个不比 key 小的值进行位置互换，就这样一直比较，最终将 key 和第一个不比 key 小的值位置互换，至此第一遍检索结束，此时 key 左边的元素全部小于 key,右边的元素全部不小于 key,相当于已经为 key 排好了序。然后对两边的子数组分别调用 QUICK_SORT(int *a,int p,int r)函数，递归地进行排序。即可完成排序。（4）计数排序：
8、开辟一个有足够大空间的新的数组 C，使得将要进行排序的数组的最大元素能存放到与其值相等下标的位置上去，并将 C 数组中所有元素初始化为 0，然后对于包含待排序元素的数组 A，从左往右，依次检索，没检索一个元素，就将 C 数组中此元素的值对应下标的元素的值加 1，检索完成，就得到 A 中全部元素出现的次数，然后对于 C 数组，将前一个元素的值与当前元素的值相加赋值给当前元素，重复此过程，直到结束，此时便可以得到 A 中元素在新的数组 B 中的下标值。然后从后往前，依次进行将 A 中元素放在 B 中相应的位置上。排序结束。3.3 调试分析 先随机产生 1000000 个 029999 之间的数，然
9、后调用排序算法，进行排序，得到排序算法的执行时间并将结果和最终得到的排序之后的数据写入到文件中去。分别如下面所示（由于数据过多，此处只显示显示部分结果）：插入排序：排序前（随机产生的数据(部分)）：排序后的数据（部分）：堆排序：排序前（随机产生的数据（部分） ）： 排序后的数据（部分）：快速排序：排序前（随机产生的数据（部分） ）：排序后的数据（部分）：计数排序：排序前（随机产生的数据（部分） ）：排序后的数据（部分）：在编写实现此功能的程序时，主要遇到了以下问题：（1） 随机产生数字的问题：开始用到了 rand()函数，产生 1000000 个数字，结果发现每一次产生的随机数字开头的都是数字
10、 41，此现象并不符合随机产生，觉得出现了问题，上网查找得知rand()函数产生随机数的原理是选取一个数为随机种子，然后根据某种数学公式推导出一系列的数组，即就是产生得到的随机数，srand()函数的作用就是初始化随机种子，运用 time()函数得到的不同时刻的时间是不一样的，因此用 srand()每次产生数字才是真正意义上的随机，用此随机种子运算得到的随机数没有出现重复，即在程序开始添加上 srand(time(0)，问题解决。（2） 开辟大数组在此次的算法设计中，开始计划每个算法产生 50000 个 019999 之间的数，观察算法消耗的时间，比较其性能。结果对于计数排序，始终显示耗时 0
11、s，开始以为程序写错了，或是编译器的问题，在别的计算机上测试，依旧是 0s，后来决定开大数组进行测试，测试到 500000 时程序异常终止，测试 200000 时可以运行，查找资料，发现局部变量默认在栈上分派空间，vc 默认是 1M，一个 int 型的数据占 4 个字节，这样最大可以申请 1024*1024/4=264144 个字节，考虑到系统自身占用的最大值是 25000 个因此只能开辟到 240000 个左右的空间，用堆内存可以实现上面的大数组，int *A=(int *)malloc(1000000*sizeof(int);问题解决。（3） 快速排序快速排序每次执行都异常退出，于是测试小
12、数组，采用单步执行进行调试，发现程序每次 QUICK_SORT()函数中出现异常，反复调试几次，都是上述情况。分析程序发现，每次当 q=r(即就是应该跳出此次递归时 ) 程序并未正常跳出此次递归，反而在程序里不停做错误循环，于是发现应该是判断语句出现问题，加入 else return 问题解决。如下所示时 QUICK_SORT()函数（4） 计数排序计数排序在执行过程中并未出现什么问题，但是在最后的输出结果中第一个值始终是负值，其余都正常。反复测试都是上述结果，由于数据太多，难以进行分析，于是选取小数组，测试，也是上述结果。暂时屏蔽掉 4 个 for 循环中最后一个，添加一步半路输出，对结果进
13、行分析，发现没有问题，于是研究最后一个 for 循环，发现赋值时直接跳过了第 0 号单元，更改程序，从第 0 号开始，问题解决。3.4 用户手册 （略）3.5 测试结果 （略）4 小结 数据结构是一门实践性很强的课，课程设计可以很好地将学到的知识投入到实践中，计算机本就不应该脱离实际，解决实际问题才是学习计算机的目的。通过课程设计可以真正地将学到的知识与实际问题结合。5 程序清单（见附录）6、参考文献 1 严蔚敏，吴伟民 编著. 数据结构(C 语言版)-北京: 清华大学出版社2007.2 严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)-北京: 清华大学出版社， 2007.3 网上搜
14、索相关程序作为参考7、程序运行结果运行截图（由于文件数据过多，此处只截取部分，具体文件位置已在 txt 文档里面标明）插入排序：堆排序：快速排序：计数排序：附录 1 （1） 插入排序：/数据结构课程设计第九章插入排序/wsrelea_2015_9_13#define N 1000000#include #include #include #include int *INSERTION_SORT (int *a)for(int j=1;j=0 & aikey) /用 key 进行标记，每一个与 key 进行比较，若是小于 key，就将其往后移，用 key 和它的前一个数进行比较ai+1=ai;i
15、=i-1;ai+1=key;return a;int main ()srand(time(0);clock_t start,finish;double duration = 0.0;FILE *fp;int *a=(int *)malloc(1000000*sizeof(int);for (int i=0; i#include #include #include int length=N;int heap_size=N;/LEFT 函数和 RIGHT 函数操作都要从 A1开始，不能用到第 0 号元素。/求结点的左子结点的编号int LEFT(int i)return 2*i;/求结点的右子结点的编号int RIGHT(int i)return 2*i+1;/维持堆的特性，使得根的值是三个结点（根节点和左右子结点）中值最大的,从上往下沿一条路径检查到底void MAX_PEAPIFY(int *A,int i)int largest; /标记出三个结点中最大的那一个int l=LEFT(i);int r=RIGHT(i);if (lAi)largest=l;else largest=i;if (rAlargest)largest=r;if (largest!=i)int ex=Ai; /exchange(Ai,Alargest)Ai=Alarges
