下载文档原格式
XX学院信息科学与工程系课程设计说明书课程名称:数据结构课程代码:题目: 快速排序与归并排序年级/专业/班:学生姓名: 奉XX学号: 1440000000指导教师: 易开题时间: 2015 年 12 月 30 日完成时间: 2016 年 1 月 10 日目录摘要 (1)一、引言 (3)二、设计目的与任务 (3)1、课程设计目的 (3)2、课程设计的任务 (3)三、设计方案 (3)1、需求分析 (3)2、概要设计 (4)3、详细设计 (5)4、程序清单 (13)四、调试分析与体会 (19)五、运行结果 (20)六、结论 (24)七、致谢 (24)八、参考文献 (25)摘要数据结构课程设计，列举了数据结构课程设计实例，通过综合训练，能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，最终目的是帮助学生系统地掌握数据结构的基本内容，并运用所学的数据结构知识去解决实际问题。
其中内容包括数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等关键字：数据结构；分析；掌握AbstractData structure course design, lists the data structure course design as an example, through the comprehensive training, to cultivate students' practical analysis and solve problems in many aspects, programming, and hands-on ability, the ultimate goal is to help students to systematically master the basic content of data structure, and using the data structure of knowledge to solve practical problems. Content including array, linked list, stack and queue, recursion, tree and forest, graph, heap and priority queue, the structure of the collection and search, sorting, indexing and hashing structure, etcKeywords:data structure；Analysis；master《数据结构》课程设计----快速排序与归并排序一、引言二、将一组数据运用快速排序与归并排序进行排序，要求使用递归与非递归方法三、本次课程设运用到了数组、链接表、栈、递归、排序等结构。
.大连科技学院数据结构课程设计题目排序综合学生专业班级指导教师职称副教授所在单位信息科学系软件教研室教学部主任完成日期2013 年1月11 日.课程设计报告单学号专业班级网络工程11-1考核项目评分备注平时工作态度及遵守纪律情况1（10 分）掌握基本理论、关键知识、基本技能的程度和2阅读参考资料的水平（10 分）独立工作能力、综合运用所学知识分析和解决3问题能力及实际工作能力提高的程度（20 分）完成课程设计说明书及软件的情况与水平（小组分工情况、规性、整洁清楚、叙述完整性、4思路清晰程度、工作量及实际运行情况和创新性）（60 分）总评成绩综合评定：（优、良、中、及格、不及格）指导教师签字：2013年1月11日数据结构课程设计任务书一、任务及要求：1.设计（研究）任务和要求研究容：排序综合任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。
（2）对指导教师下达的题目进行系统分析。
（3）根据分析结果完成系统设计。
（4）编程：在计算机上实现题目的代码实现。
（5）完成对该系统的测试和调试。
（6）提交课程设计报告。
要求完成课程设计报告3000 字以上 (约二十页 )。
完成若干综合性程序设计题目，综合设计题目的语句行数的和在100 行语句以上。
2.原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
提高程序设计和调试能力。
学生通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3.参考题目：二、工作量2 周（ 10 个工作日）时间三、计划安排第 1 个工作日：查找相关资料、书籍，阅读示例文档，选择题目。
第 2 个工作日－第 3 个工作日：设计程序结构、模块图。
第 4 个工作日－第 9 个工作日：完成程序的编码，并且自己调试、测试。
穿插进行课程设计报告的撰写。
第 10 个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。
数据结构课程设计报告几种排序算法的演示1、需求分析:运行环境:Microsoft Visual Studio 20052、程序实现功能:3、通过用户键入的数据, 经过程序进行排序, 最后给予数据由小到大的输出。
排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。
每种排序过程中均显示每一趟排序的细节。
程序的输入:输入所需排序方式的序号。
输入排序的数据的个数。
输入具体的数据元素。
程序的输出:输出排序每一趟的结果, 及最后排序结果1、设计说明:算法设计思想:a交换排序（冒泡排序、快速排序）交换排序的基本思想是: 对排序表中的数据元素按关键字进行两两比较, 如果发生逆序（即排列顺序与排序后的次序正好相反）, 则两者交换位置, 直到所有数据元素都排好序为止。
b插入排序（直接插入排序、折半插入排序）插入排序的基本思想是: 每一次设法把一个数据元素插入到已经排序的部分序列的合适位置, 使得插入后的序列仍然是有序的。
开始时建立一个初始的有序序列, 它只包含一个数据元素。
然后, 从这个初始序列出发不断插入数据元素, 直到最后一个数据元素插到有序序列后, 整个排序工作就完成了。
c选择排序（简单选择排序、堆排序）选择排序的基本思想是: 第一趟在有n个数据元素的排序表中选出关键字最小的数据元素, 然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素, 依次重复, 每一趟（例如第i趟, i=1, …, n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素, 作为有序数据元素序列的第i个数据元素。
等到第n-1趟选择结束, 待排序数据元素仅剩下一个时就不用再选了, 按选出的先后次序所得到的数据元素序列即为有序序列, 排序即告完成。
d归并排序（两路归并排序）1、两路归并排序的基本思想是: 假设初始排序表有n个数据元素, 首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项）, 先做两两归并, 得n/2上取整个长度为2的归并项（如果n为奇数, 则最后一个归并项的长度为1）；再做两两归并, ……, 如此重复, 最后得到一个长度为n的有序序列。
目录1.引言............................................................................................................................ 错误！未定义书签。
2.需求分析.................................................................................................................... 错误！未定义书签。
3.详细设计.................................................................................................................... 错误！未定义书签。
3.1 直接插入排序................................................................................................ 错误！未定义书签。
3.2折半排序......................................................................................................... 错误！未定义书签。
3.3 希尔排序........................................................................................................ 错误！未定义书签。
3.4简单选择排序................................................................................................. 错误！未定义书签。
《数据结构》课程设计报告一、课程目标《数据结构》课程旨在帮助学生掌握计算机科学中数据结构的基本概念、原理及实现方法，培养其运用数据结构解决实际问题的能力。
本课程目标如下：1. 知识目标：（1）理解数据结构的基本概念，包括线性表、栈、队列、串、数组、树、图等；（2）掌握各类数据结构的存储表示和实现方法；（3）了解常见算法的时间复杂度和空间复杂度分析；（4）掌握排序和查找算法的基本原理和实现。
2. 技能目标：（1）能够运用所学数据结构解决实际问题，如实现字符串匹配、图的遍历等；（2）具备分析算法性能的能力，能够根据实际问题选择合适的算法和数据结构；（3）具备一定的编程能力，能够用编程语言实现各类数据结构和算法。
3. 情感态度价值观目标：（1）培养学生对计算机科学的兴趣，激发其探索精神；（2）培养学生团队合作意识，提高沟通与协作能力；（3）培养学生面对问题勇于挑战、善于分析、解决问题的能力；（4）引导学生认识到数据结构在计算机科学中的重要地位，激发其学习后续课程的兴趣。
本课程针对高年级学生，课程性质为专业核心课。
结合学生特点，课程目标注重理论与实践相结合，强调培养学生的实际操作能力和解决问题的能力。
在教学过程中，教师需关注学生的个体差异，因材施教，确保课程目标的达成。
通过本课程的学习，学生将具备扎实的数据结构基础，为后续相关课程学习和职业发展奠定基础。
二、教学内容根据课程目标，教学内容主要包括以下几部分：1. 数据结构基本概念：线性表、栈、队列、串、数组、树、图等；教学大纲：第1章 数据结构概述，第2章 线性表，第3章 栈和队列，第4章 串。
2. 数据结构的存储表示和实现方法：教学大纲：第5章 数组和广义表，第6章 树和二叉树，第7章 图。
3. 常见算法的时间复杂度和空间复杂度分析：教学大纲：第8章 算法分析基础。
4. 排序和查找算法：教学大纲：第9章 排序，第10章 查找。
教学内容安排和进度如下：1. 第1-4章，共计12课时，了解基本概念，学会使用线性表、栈、队列等解决简单问题；2. 第5-7章，共计18课时，学习数据结构的存储表示和实现方法，掌握树、图等复杂结构；3. 第8章，共计6课时，学习算法分析基础，能对常见算法进行时间复杂度和空间复杂度分析；4. 第9-10章，共计12课时，学习排序和查找算法，掌握各类算法的实现和应用。
数据结构课程设计报告几种排序算法的演示一、需求分析：1、运行环境：Microsoft Visual Studio 20052、程序实现功能：通过用户键入的数据，经过程序进行排序，最后给予数据由小到大的输出。
排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。
每种排序过程中均显示每一趟排序的细节。
3、程序的输入：输入所需排序方式的序号。
输入排序的数据的个数。
输入具体的数据元素。
4、程序的输出：输出排序每一趟的结果，及最后排序结果二、设计说明：1、算法设计思想：a交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。
b插入排序（直接插入排序、折半插入排序）插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。
开始时建立一个初始的有序序列，它只包含一个数据元素。
然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。
c选择排序（简单选择排序、堆排序）选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。
等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。
d归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。
《数据结构》课程设计实验报告题目：排序（必做题）姓名：学号：指导老师：时间：2015.09.03目录一、设计内容和要求 (3)二、算法思想描述 (3)1. 希尔排序 (3)2. 快速排序 (3)3. 堆排序 (4)4. 归并排序 (7)5. 性能分析 (8)三、程序结构 (10)四、结果与分析 (10)五、收获与体会 (12)一、设计内容和要求设计内容：排序算法的实现与比较要求：编程希望实现希尔、快速、堆排序、归并排序算法。
要求随机产生10000个数据存入数据文件，然后读数据文件，分别采用不同的排序方法进行排序，将结果存入文件中。
二、算法思想描述1.希尔排序先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
图解：2.快速排序首先选一个枢轴k（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于枢轴k，后一部分记录的关键码均大于或等于枢轴k，然后分别对这两部分重复上述方法，直到整个序列有序。
经过一次划分后枢轴k再对1、2区分别再进行快速排序3.堆排序筛选：假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1] ~ r[m]满足堆的条件），则筛选算法用伪代码可描述为：图解：堆排序：堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。
（1）用大根堆排序的基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys ≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
《数据结构》课程设计报告专业班级姓名学号指导教师起止时间课程设计：排序综合一、任务描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。
（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。
并把排序后的结果保存在不同的文件中。
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
要求：根据以上任务说明，设计程序完成功能。
二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）随机生成N个整数，存放到线性表中；（2）起泡排序并计算所需时间；（3）简单选择排序并计算时间；（4）希尔排序并计算时间；（5）直接插入排序并计算所需时间；（6）时间效率比较。
2、数据对象分析存储数据的线性表应为顺序存储。
三、数据结构设计使用顺序表实现，有关定义如下：typedef int Status;typedef int KeyType ; 直接插入排序0. 退出系统（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：主控菜单项选择函数menu()创建排序表函数InitList_Sq()起泡排序函数Bubble_sort()简单选择排序函数SelectSort()希尔排序函数ShellSort();对顺序表L进行直接插入排序函数Insertsort()（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。
其中main()是主函数，它负责调用各函数。
进行调用菜单函数menu()，根据选择项0~4调用相应的函数。
main()函数使for循环实现重复选择。
其循环结构如下：for (;;){long start,end;switch(menu()){case 1:printf("* 起泡排序*\n");start=clock();Bubble_sort(L);end=clock();printf("%d ms\n",end-start);fp=fopen("D: 起泡排序.txt","w");if(fp==NULL)xt","w");if(fp==NULL)xt","w");if(fp==NULL)Ney,[j].key)){flag=1; 共通过n－1趟,得到一个按排序码从小到大排列的有序序列流程图：NN代码描述：void SelectSort(SqList &L){ ] 中选择key最小的记录int k=i;for(int j=i+1;j<= ; j++)if ( LT[j].key,[k].key)) k=j;if(k!=i){x=[i];[i]=[j];[j]=x;}}} ey , [i-dk].key )){[0]= [i];int j;for(j=i-dk;(j>0)&&(LT [0].key , [j].key ));j-=dk)[j+dk]= [j];[j+dk]= [0];}}}void ShellSort(SqList &L,int dlta[],int t)NNey,[i-1].key)) ey,[j].key);j--){[j+1]=[j];ey的元素[j+1]=[0]; //将暂存在r[0]中的记录插入到正确位置}// printf("%d ",[i]);}算法的时间复杂度分析：O（n2）五、测试数据和结果1、测试数据随机产生30000个数2、测试结果本程序在VC++环境下实现，下面是对以上测试数据的运行结果。
《数据结构》课程设计报告专业计算机科学与技术班级(1)姓名学号指导教师起止时间2011.10~2011.12课程设计：排序综合一、任务描述（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。
并把排序后的结果保存在不同的文件中。
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）显示随机数：调用Dip()函数输出数组a[]。
数组a[]中保存有随机产生的随机数。
（2）直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。
（3）冒泡排序：如果有n个数，则要进行n-1趟比较。
在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。
（4）希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
（5）直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。
设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。
（6）显示各排序算法排序后的的数据和时间效率，并比较找出其中2种较快的方法。
2、数据对象分析排序方式：直接选择排序、冒泡排序、希尔排序、直接插入排序显示排序后的的数据和时间效率。
三、数据结构设计1.主要全程变量及数据结构数据结构：typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;2.算法的入口参数及说明#include <stdio.h>#define MAXSIZE 20#define LT(a,b) ((a)<(b)) //宏定义typedef int KeyType; //定义关键字KeyType为inttypedef int InfoType; //定义关键字InfoType为inttypedef struct{ //RedType结构定义KeyType key;InfoType otherinfo; //记录中其他信息域的类型}RedType;typedef struct{ //SqList结构定义RedType r[MAXSIZE+1]; //定义大小int length; //length为待排记录个数}SqList;四、功能设计（一）主控菜单设计为实现排序的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。
程序运行后，给出11个菜单项的内容和输入提示，如下：欢迎来到排序综合系统！菜单(1)---直接插入排序(2)---直接选择排序(3)---冒泡排序(4)---快速排序(5)---堆排序(6)---时间效率比较(7)---显示随机数(0)---退出系统请在上述序号中选择一个并输入：（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：●主控菜单项选择函数menu_select()●插入排序函数：InsertS ort()●选择排序函数：SelectSort()●冒泡排序函数：BubbleSort()●堆排序函数：heapsort()（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。
其中main()是主函数，它进行菜单驱动，根据选择项1~0调用相应的函数。
（四）函数实现#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <windows.h>#include <time.h>#define N 30000void Wrong(){printf("\n=====>按键错误!\n");getchar();}void Disp(int a[]){int i;system("cls");for(i=0;i<N;i++){if((i-1)%10==9)printf("\n");printf("%-7d",a[i]);}}void InsertSort(int a[],int p) //插入排序{int i,j,temp;for(i=1;i<N;i++){temp=a[i];for(j=i;j>0&&a[j-1]>temp;j--)a[j]=a[j-1];a[j]=temp;}}void SelectSort(int a[],int p) //选择排序{int i,j,k;for(i=0;i<N-1;i++){k=i;for(j=i+1;j<N;j++)if(a[j]<a[k])k=j;if(k!=i){int temp;temp=a[k];a[k]=a[i];a[i]=temp;}}}void BubbleSort(int a[],int p) /*冒泡排序算法*/{int i,j,temp;for (i=0;i<N-1;i++){for (j=N-1;j>i;j--) /*比较,找出本趟最小关键字的记录*/ if (a[j]<a[j-1]){temp=a[j]; /*进行交换,将最小关键字记录前移*/a[j]=a[j-1];a[j-1]=temp;}}}void creatheap(int a[],int i,int n) //创建堆{int j;int t;t=a[i];j=2*(i+1)-1;while(j<=n){if((j<n)&&(a[j]<a[j+1]))j++;if(t<a[j]){a[i]=a[j];i=j;j=2*(i+1)-1;}elsej=n+1;}a[i]=t;}void heapsort(int a[],int n,int p) //堆排序{int i;int t;for(i=n/2-1;i>=0;i--)creatheap(a,i,n-1);for(i=n-1;i>=1;i--){t=a[0];a[0]=a[i];a[i]=t;creatheap(a,0,i-1);}}void quicksort(int a[],int n,int p){int i,j,low,high,temp,top=-1;struct node{int low,high;}st[N];top++;st[top].low=0;st[top].high=n-1;while(top>-1){ low=st[top].low;high=st[top].high;top--;i=low;j=high;if(low<high){ temp=a[low];while(i!=j){ while(i<j&&a[j]>temp)j--;if(i<j){a[i]=a[j];i++;}while(i<j&&a[i]<temp)i++;if(i<j){a[j]=a[i];j--;}}a[i]=temp;top++;st[top].low=low;st[top].high=i-1; top++;st[top].low=i+1;st[top].high=high; }}}double TInsertSort(int a[],int p){int i;int b[N];for(i=0;i<N;i++)b[i]=a[i];LARGE_INTEGER m_liPerfFreq={0}; QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);InsertSort(b,p);LARGE_INTEGER liPerfNow={0};QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=6){Disp(b);getchar();}printf("\n用直接插入排序法用的时间为%f秒；",time);FILE *fp;fp=fopen("直接插入排序.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",b[i]);fclose(fp);return(time);}double TSelectSort(int a[],int p){int i;int b[N];for(i=0;i<N;i++)b[i]=a[i];LARGE_INTEGER m_liPerfFreq={0}; QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);SelectSort(b,p);if(p!=6){Disp(b);getchar();}LARGE_INTEGER liPerfNow={0};QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;printf("\n用直接选择排序法用的时间为%f秒；",time);FILE *fp;fp=fopen("直接选择排序.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",b[i]);fclose(fp);return(time);}double TBubbleSort(int a[],int p){int i;int b[N];for(i=0;i<N;i++)b[i]=a[i];LARGE_INTEGER m_liPerfFreq={0}; QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);BubbleSort(b,p);LARGE_INTEGER liPerfNow={0};QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=6){Disp(b);getchar();}printf("\n用冒泡排序法用的时间为%f秒；",time);FILE *fp;fp=fopen("冒泡排序.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",b[i]);fclose(fp);return(time);}double Theapsort(int a[],int n,int p){int i;int b[N];for(i=0;i<N;i++)b[i]=a[i];LARGE_INTEGER m_liPerfFreq={0}; QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);heapsort(b,N,p);LARGE_INTEGER liPerfNow={0};QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=6){Disp(b);getchar();}printf("\n用堆排序法用的时间为%f秒；",time);FILE *fp;fp=fopen("堆排序.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",b[i]);fclose(fp);return(time);}double Tquicksort(int a[],int n,int p){int i;int b[N];for(i=0;i<N;i++)b[i]=a[i];LARGE_INTEGER m_liPerfFreq={0}; QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGER m_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);quicksort(b,N,p);LARGE_INTEGER liPerfNow={0};QueryPerformanceCounter(&liPerfNow);double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if(p!=6){Disp(b);getchar(); }printf("\n用快速排序法用的时间为%f秒；",time);FILE *fp;fp=fopen("快速排序.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",b[i]);fclose(fp); return(time);}void BubleSort(double a[]) //时间数组的冒泡排序{int i,j;double temp;for(i=1;i<6;i++){for(j=4;j>=i;j--)if(a[j+1]<a[j]){temp=a[j+1];a[j+1]=a[j];a[j]=temp;}}}void menu(){printf(" 欢迎来到排序综合系统! \n"); printf(" ============================================== \n"); printf(" \n"); printf(" 菜单 \n"); printf(" \n"); printf(" \n"); printf(" (1)---直接插入排序 \n"); printf(" (2)---直接选择排序 \n"); printf(" (3)---冒泡排序 \n"); printf(" (4)---快速排序 \n"); printf(" (5)---堆排序 \n"); printf(" (6)---时间效率比较 \n"); printf(" (7)---显示随机数 \n"); printf(" (0)---退出系统 \n"); printf("\n 请在上述序号中选择一个并输入: "); }void main(){int i,p,a[N];srand((int)time(NULL)); /*随机种子*/for(i=0;i<N;i++)a[i]=rand()%50000+1;while(1){system("cls");menu();scanf("%d",&p);if(p==0){printf("===>谢谢使用!\n");getchar();break;}double TIMES[5],TIMES1[5];//时间数组switch(p){case 1:TInsertSort(a,p);printf("\n请按任意键继续...");getchar();break;case 2:TSelectSort(a,p);printf("\n请按任意键继续...");getchar();break;case 3:TBubbleSort(a,p);printf("\n请按任意键继续...");getchar();break;case 4:Tquicksort(a,N,p);printf("\n请按任意键继续...");getchar();break;case 5:Theapsort(a,N,p);printf("\n请按任意键继续...");getchar();break;case 6:system("cls");TIMES1[1]=TIMES[1]=TInsertSort(a,p);TIMES1[2]=TIMES[2]=TSelectSort(a,p);TIMES1[3]=TIMES[3]=TBubbleSort(a,p);TIMES1[4]=TIMES[4]=Tquicksort(a,N,p);TIMES1 [5]=TIMES[5]=Theapsort(a,N,p);getchar();BubleSort(TIMES);printf("\n\n");{printf("排序这组数据两种较快的排序法分别是：\n");if(TIMES[1]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[1]); if(TIMES[1]==TIMES1[2]) printf("直接选择排序:%f秒!\n",TIMES[1]);if(TIMES[1]==TIMES1[3]) printf("冒泡排序:%f秒!\n",TIMES[1]);if(TIMES[1]==TIMES1[4]) printf("快速排序:%f秒!\n",TIMES[1]);if(TIMES[1]==TIMES1[5]) printf("堆排序:%f秒!\n",TIMES[1]);if(TIMES[1]!=TIMES[2]){if(TIMES[2]==TIMES1[1]) printf("直接插入排序:%f秒!\n",TIMES[2]); if(TIMES[2]==TIMES1[2]) printf("直接选择排序%f秒!\n",TIMES[2]);if(TIMES[2]==TIMES1[3]) printf("冒泡排序%f秒!\n",TIMES[2]);if(TIMES[2]==TIMES1[4]) printf("快速排序%f秒!\n",TIMES[2]);if(TIMES[2]==TIMES1[5]) printf("堆排序%f秒!\n",TIMES[2]);}} printf("\n请按任意键继续...");srand((int)time(NULL));for(i=0;i<N;i++) {a[i]=rand()%30000+1;} getchar();break;case 7:Disp(a);FILE *fp;fp=fopen("随机数.txt","w");for(i=0;i<N;i++)fprintf(fp,"%d ",a[i]);fclose(fp);getchar();printf("\n请按任意键继续...");getchar();break;default:Wrong();printf("\n请按任意键继续...");getchar();break;}}}五、测试数据和结果本程序在VC++环境下实现，下面是对以上测试数据的运行结果。
