内部排序算法比较 班级： 姓名： 学号： 完成日期： 题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 一．需求分析 1.对常用的6 种内部排序算法进行比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。 2.待排序表的表长不小于 100；其中的数据要用伪随机数产生程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动） 3.最后要对结果作出简单分析，包括对各组数据得到结果波动大小的解释。 二．概要设计 1 .主界面设计 对六种内部排序算法进行比较，可通过随机数程序产生几组数，要求用户手动输入产生随机数的个数。运行界面如图所示： 选择 1 运行程序，选择 2 退出程序 2 ．存储结构设计 本程序采用顺序表结构，具体结构定义如下： typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList; 3 .系统功能设计 1）分配内存空间。创建顺序表 2）利用伪随机数产生程序产生随机数，作为程序运行的数据 3）实现每种排序算法的功能函数 三．模块设计 1 .模块设计 2 .系统子程序及功能设计 本系统共设置 13 个函数，其中包括主函数。各函数名及功能说明如下。 1） void addlist(SqList &L) //建立个空顺序表 2） void random(SqList &L) //随机数产生函数 3） void memory(SqList &M,SqList &L) //记录 L，以保证每个排序函数使用一组随机数 4） void BubbleSort(SqList &L) //冒泡排序 5） void InsertSort(SqList &L) //直接插入排序 6） void SelectSort(SqList &L) //选择排序 7） int Partition(SqList &L,int low,int high) //返回快速排序枢轴的位置 8） void QSort(SqList &L,int low,int high) //对子序列作快速排序 9） void QuickSort(SqList &L) //对数序表作快速排序 10）void ShellSort (SqList &L) //希尔排序 11）void HeapAdjust(SqList &L,int s,int m )//堆排序算法子程序 12）void HeapSort(SqList &L) //对顺序表进行堆排序 13）void main() //主函数，调用各模块函数 3 .函数主要调用关系 主程序模块 随机数产生模块 排序算法模块 四．详细设计 1 .数据类型定义 typedef struct { int key; }ElemType; ty...
