内部排序教学软件(c语言)

1、内部排序教学软件班 级软件098班小 组 成 员 指 导 教 师 开 发 时 间 2010/6/15数据结构课程设计course design of data structure一、系统简介内部排序教学软件的总体目标：在turbo c2.0 的开发环境下，利用所学c语言和数据结构的相关知识，开发一个具有良好人机界面的内部排序教学软件，实现各种内部排序，并能使用户通过其显示结果对每种排序方法的性能有一个直观的了解，从而达到教学的目的。二、需求分析内部排序教学软件主要实现以下功能:（1）界面友好，易与操作。采用菜单或其它人机对话方式进行选择。（2）实现各种内部排序。包括冒泡排序，直接插入排序，直接

2、选择排序，快速排序，堆排序。（3）待排序的元素的关键字为整数。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。（4）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。三、概要设计1、系统功能结构图冒泡排序快速排序堆排序产生顺序数列退出系统内部排序教学软件菜单简单选择排序插入排序产生随机数列产生逆序数列2、重要数据的数据结构设计设计关键字的数据结构类型为int整形, typedef int keytype;定义关键字结构体rec包含属性内容: keytype key;定义结构体顺序表: sq

3、list;3、函数设计1基本操作：bubblesort(struct rec r,int n) /*冒泡排序*/操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。selectsort(struct rec r,int n) /*简单选择*/操作结果：进行简单排序，返回关键字比较次数c和移动次数sint partition(struct rec r,int low,int high)/*快速排序*/操作结果：进行快速排序，返回关键字比较次数c和移动次数sinsertsort(struct rec r,int n)/*直接插入*/操作结果：进行插入排序，返回关键字比较次数c和移动次数ssi

4、ft(struct rec r,int l,int m) /*堆排序*/操作结果：进行堆排序，返回关键字比较次数c和移动次数s。copy(struct rec ls,struct rec rs,int n)/*将一个数组中的数全部复制到另一个数组中*/shunxu(struct rec r,int n)/*产生顺序数列*/nixu(struct rec r,int n)/*产生逆序数列*/void output(struct rec r,int n)/*输出函数*/2本程序包含两个模块：1）主程序模块void main()初始化；do 接受命令； 处理命令； while(“命令”！=“退出”)

5、； 四、详细设计1、系统主函数 main()设计结束显示主菜单并响应用户操作开始2、主菜单模块函数 menu() 设计choose!=5插入排序choose接收用户选择显示主菜单开始清屏屏幕 产生顺序数列产生逆序数列退出系统产生随机数列堆排序简单选择排序快速排序冒泡排序 yn五测试情况及调试中问题与解决方案：因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小(规模)；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等。不同条件下，排序方法的选择(1)若n较小(如n50)，可采用直接插入或直

6、接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为o(nlgn)的排序方法：快速排序、堆排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和

7、直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。 (4)有的语言(如fortran，cobol或basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。(5)书上给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种

8、情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令ti=i(0in)，若排序算法中要求交换ri和rj，则只需交换ti和tj即可；排序结束后，向量t就指示了记录之间的顺序关系： rt0.keyrt1.keyrtn-1.key 若要求最终结果是： r0.keyr1.keyrn-1.key则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是o(n)。 六心得体会与小结：心得：我选了排序这一题目，感觉只要掌握了几个典型排序算法这次课设不会感觉难度很大，通过这次课设，我进一步加深了对c语言的理解，特别是对数据结构中内

9、部排序这一经典内容的深刻领会。提高了对c语言的运用能力，为今后其他后继课程做了很多铺垫。小结：1.学会使用随机函数rand( ) % 为数组赋初值2.在做此程序之前基本上是在理解了各种排序过程以后完成的3.对排序算法的总结：(1)若n较小(如n50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为o(nlgn)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最

10、好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。4.学会使用计时函数clock()，要在头文件上添加#include三实验过程截图（用户使用说明）1程序主界面 2排序 为了方便测试算法我在程序中预先编入了一串未排序好的数列。下面是各算法对这串数列的排序。 1冒泡排序 2简单选择排序 3快速排序4插入排序5堆排序 3 产生随机，正序，逆序数列1 产生随机数列 2 产生顺序数列3 产生逆序数列4 各排序算法时间比较在这里我只选取了随机生成数列中的数据来进行各排序算法时间比较，其中用到了c语言中自带的clock计时函数，时间的单位是毫秒，至于顺序和逆序生成的数据我没有进行测试。下面是各算法的时间比较： 致 谢首先感谢我的指导老师杨文姬老师，他在我的课程设计过