数据结构排序算法上机报告

含有源代码。。。

重庆邮电大学

数据结构上机报告

题目名称排序算法及其性能分析

学院计算机科学与技术学院

姓名吴贤伟，魏锋

学号 2009211975，2009211979

指导老师

含有源代码。。。

目录

一概述 ............................................... 3

二课程设计思想 ............................... 4

三程序分析 ....................................... 5

四程序运行结果 ............................... 7

五课程设计的不足及自我感受 ...... 10

（1）不足之处 ............................ 10

（2）自我感受 ............................ 10

六参考文献 ..................................... 11

附录源代码 ..................................... 11

含有源代码。。。

一概述

1 课程设计的目的

编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中

2课程设计的要求

（1）．问题分析和任务定义。

编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中

（2）．逻辑设计。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。

（3）．物理设计。定义相应的存储结构并写出各函数的伪码算法。

（4）．详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。

（5）．程序编码。

（6）．程序调试与测试。

（7）．结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。

含有源代码。。。

（8）．编写设计报告。

二课程设计思想

排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。内部排序算法主要分为5 大类，有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等

程序设计的总体思路：先建立主函数main()函数，在建立其它几个排序函数：shell排序(void shellSort(SqList R)),快速排序（void QuickSort(SeqListR,int low ,int high)）,堆排序（void Heapify(SeqListR,intlow,int high)）,归并排序（void Merge(SqListR,intlow,int high)）;还有为了增加程序的可操作性，还在其过程中增加了其它函数来让读者选择函数的其它的功能。

希尔排序的的基本思想：现将整个待排序记录分割成若干子程序分别进行直接插入排序，待整个程序列重的记录“基本有序”的时候在对全体记录进行一次直接插入排序。

快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准点）（pivot）,将所

含有源代码。。。

有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的放置到它的位置之后（作为一次划分过程）。之后对所分的两部分分别进行上述过程，知道每个部分只有一个记录为止。

归并的基本思想：假设初始序列n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到【n/2】个长度为2的子序列，在两两归并·····如此重复，直到长度为n的有序序列为止。

堆排序的基本思想：将元素构成大根堆或者小根堆，输出堆顶的元素之后，把剩余的n-1个元素构成一个新的堆，得到n个元素中的次小值。如此反复的执行，便能得到一个有序序列，这个过程叫做堆排序。

三程序分析

1）.选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下4 点：

待排序的记录数目n 的大小。

记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。

关键字的结构及其分布情况。

对排序稳定性的要求。

含有源代码。。。

2.程序运行函数调用图

含有源代码。。。

四程序运行结果

1. 判断是否有数据文件，在没有的情况下，提示打开文件失败，是否需要建立新的文件。

2. 从数据文件中读取数据，如果数据文件中没有数据，提示是否输入数据，1：输入需要输入数据的个数，同时输入每个数据： 2：退出

含有源代码。。。

如果数据文件中有数据，则从文件中读取数据，跳过从键盘输入数据。

3.堆排序的结果，还有比较的次数和交换的次数：

4.归并排序的结果，还有比较的次数和交换的次数：

含有源代码。。。

5.快速排序的结果：

6.希尔排序的结果：

含有源代码。。。

五课程设计的不足及自我感受

（1）不足之处

1． 程序在执行的过程中不能清楚看到程序每一个执行的步骤过

程，给人不是很直观。

2． 程序代码不是很精简，思想不是很完美。

3． 当文件中只有一个数据时，程序提示没有数据。

（2）自我感受

1．在初期构思代码的时候，首先构造了各种算法的基本实现代码，已经能够实现四种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要计算执行的次数，由此添加了计数器，满足各种计数的需求。之后考虑如何能简化代码以实现多达四种排序算法的简单调用和性能指标。此外还添加了一系列优化，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。

2．程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。让我明白了要学习各方面的知识才能更好的做到这一点。

3．这次课设通过在网上查阅大量资料、程序以及一些学术论文，很好的对内排序算法进行了研究，特别对数据结构这门课所学到的内容付诸于实践，加深了理解。另外，还学到了一写别的方面的知识。

4.通过这次课题的研究让我们学习了很多，了解了大型程序的概念，同时也让我们掌握了其中的学习方法还有明白了团队合作的重要性。 这次课题研究还有什么不足的地方希望老师指出。

含有源代码。。。

六参考文献

【1】 严蔚敏吴伟明，《数据结构（c语言版）》清华大学出版社

【2】 谭浩强，《C程序设计（第三版）》清华大学出版社

【3】 甘玲刘达明唐雁，《解析C程序设计》清华大学出版社 附录源代码

#i …… 此处隐藏：5640字，全部文档内容请下载后查看。喜欢就下载吧 ……