文档介绍：1问题描述
本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性,如:正序、逆序和不同程度的乱序。注意采用分块调试的方法。
1. 待排序表的表长不小于100,其中数据要用的随机数产生程序产生,至少要用5组不同的输入数据体比较,比较的指标为:有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次的移动)。
2. 演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”下,用户可由键盘输入待排序表的表长和不同的测试数据的数组,每次测试完毕,列表显示各种比较指标值。
,包括对各组数据得出结果波动大小给予解析。
测试数据
由函数rand随机产生的数据,由于是随机产生的,所以在此不一一写出。
2 需求分析
由于程序中所需的数据都是有函数随机生成的整形数,不需要用户自己输入,用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。
程序输出的是对六种排序做的一些比较,即输出六种排序各排序过程中所比较的数据的个数,交换的数据的次数,和排序完成所用的时间。六种排序依次在计算机终端上显示,便于用户观察。
输入值的范围等价于程序中随机生成的数据的个数,即待排序表的表长不小于100,至少要用5组不同的输入数据体比较,比较的指标为:有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次的移动),在该程序中,随机生成的数据个数被初始化为了10000,数据越大就越容易比较。
输入N个随机整数,对这些数进行多种方法进行排序,并对这些排序做比较,在屏幕上输出每种排序方法所比较的次数,交换的次数,和用掉的时间。
任意性:系统首先生成10000个随机整数,然后分别用不同的排序方法对其进行升序排序,给出每种方法的比较次数或所用时间
友好性:界面要友好,输入有提示,尽量展示人性化
可读性:源程序代码清晰、有层次
健壮性:用户输入非法数据时,系统要及时给出警告信息
3 概要设计
typedef struct StudentData
{
int num; //存放关键字,如零时变量,还有哨兵
}Data;
typedef struct LinkList
{
int Length; //存放随机数的个数
Data Record[MAXSIZE];//用数组存放所有的随机数
}LinkList;
系统功能模块
外部功能模块图
内部排序排序的比较
random numbers
随机生成数据
Compare
比较所有排序
SelSort
选择排序
BubbleSort
冒泡排序
HeapSort
堆排序
QuickSort
快速排序
Shellsort
希尔排序
set linklist
初始化链表
图 外部功能模块图
主函数功能模块图
主函数 main()
InitLinkList(LinkList* L)
初始化链表
Show the menu
显示主界面
Compare
比较六种排序
Display
把数据写入文件
set
定义或初始化变量
图 主函数功能模块图
4详细设计
整个程序的流程图
开始界面
Compare 比较各排序
快
速
排
序
堆
排
序
选
择
排
序
冒
泡
排
序
希
尔
排
序
插
入
排
序
比较各排序
输出数据
结束
整个程序的流程图
插入排序及其主要代码
直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,它的基本操作是将一个纪录插入到已排好序的有序表中,从而得到一个新的、纪录数增1的有序表。
例如,已知待排序的一组纪录的初始排列如下所示:
R(49)、R(38)、R(65)、R(97)、R(76)、R(13)、R(27)、R(49)……(4-1)
假设在排序过程中,前4个记录已按关键字递增的次序重新排列,构成一个含4个纪录的有序序列
{ R(38)、R(49)、R(65)、R(97) } (4-2) 现要将式(4-1)中的第5个纪录插入上述序列,以得到一个新的含5个纪录的有序序列,则首先要在式(4-2)的序列中进行查找以确定R(76)、所