《数据结构》课程设计报告
专业
班级
姓名
学号
指导教师
起止时间
课程设计：排序综合
一、任务描述
利用随机函数产生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)
N
ey,[j].key))
{
flag=1; 共通过n－1趟,得到一个按排序码从小到大排列的有序序列
流程图：
N
N
代码描述：
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)
N
N
ey,[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) 主菜单显示如下：
六、结束语
本设计完成了课题要求的任务，较熟练地掌握了各种排序方法。在设计过程中，由于个别代码段设计不当多次出现程序溢出情况。在评判各种排序方法的用时上换了两种计时方
法，现在使用的这个较为准确。从结果可以看出，堆排序和快速排序这两种方法最快。当然或许还有更快的排序方法，此处没有使用并列举出来。
