内部排序算法比较

内部排序算法比较

班级： 姓名： 学号： 完成日期：

题目：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 一．需求分析

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.函数主要调用关系

13）main（） 1 2 9 3 4 12 5 10 6 8 11 7

四．详细设计

1.数据类型定义 typedef struct {

int key; }ElemType; typedef struct {

ElemType *elem; int length; }SqList;

2.全局变量定义

int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;//记录每种算法的比较，移动次数 int n；//随机数的个数

2.系统主要子程序详细设计 （1）主函数设计模块

主要是输入数据，以及程序界面的设计，调用系统的各个子程序，并输出结果。（详见源程序）

（2）随机数产生模块

利用伪随机数产生程序产生数据，并存储到顺序表中。 void random(SqList &L) {

L.length=0;

static bool first=true; if(first) {

srand(time(0)); first=false;

}//使每次产生的随机数不同 for(int i=1;i

a: { L.elem[i].key=rand(); if(L.elem[i].key>30000) goto a; ++L.length; }

（3）排序算法模块 实现冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序以及堆排序的算法。（祥见源程序） 五．测试分析

运行程序后，得到如图所示：

输入：1

输入：100

选择1重复上述步骤，输入150，200，250，300得到另外四个结果：

退出程序，请选择：2