内部排序算法实现与性能分析课程设计

目 录

1、问题描述：....................................................... 2

1.1题目内容:.................................................... 2 1.2基本要求:.................................................... 2 1.3测试数据:.................................................... 2 2、需求分析：....................................................... 2

2.1程序的基本功能:.............................................. 2 2.2输入值、输出值以及输入输出形式:.............................. 2 2.3各个模块的功能要求：......................................... 2 3、概要设计：....................................................... 3

3.1所需的ADT，每个程序中使用的存储结构设计说明 ................. 3 3.2主程序流程以及模块调用关系................................... 3 3.3每个模块的算法设计说明（流程图）............................. 4

3.3.1气泡排序： ............................................. 4 3.3.2直插排序 ............................................... 5 3.3.3选择排序 ............................................... 6 3.3.4希尔排序 ............................................... 7 3.3.5快速排序 ............................................... 8

4、详细设计：....................................................... 9

4.1函数调用关系图............................................... 9 5、各个算法实现的源程序：........................................... 9

5.1、冒泡排序及其主要算法 ....................................... 9 5.2、直接插入排序及其主要算法 .................................. 10 5.3、选择排序及其主要算法 ...................................... 10 5.4、希尔排序及其主要算法 ...................................... 11 6、调试分析：...................................................... 12 7、使用说明：...................................................... 13 8、测试结果：...................................................... 14 9、主要参考文献.................................................... 14

第 1 页 共 14 页

1、问题描述：

1.1题目内容:

内部排序算法实现与性能分析

1.2基本要求:

（1）数据结构定义

（2）利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的时间,对各种排序算法做分析比较.

1.3测试数据:

由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。

2、需求分析：

2.1程序的基本功能:

输入30000个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和时间复杂度。

2.2输入值、输出值以及输入输出形式:

由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。

程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。

2.3各个模块的功能要求：

一、随机函数：产生随机数

二、选择排序函数：对随机数进行选择排序 三、起泡排序函数：对随机数进行气泡排序

四、直接插入函数：对随机数进行直接插入排序 五、希尔排序函数：对随机数进行希尔排序 六、快速排序函数：对随机数进行快速排序 七、主函数

第 2 页 共 14 页

3、概要设计：

3.1所需的ADT，每个程序中使用的存储结构设计说明

typedef struct {

int key;

}ElemType;//元素类型 typedef struct

{

ElemType *elem; int length;

}SqList;//顺序表类型

3.2主程序流程以及模块调用关系

主函数 main（）

初始化变量 x,i; ; 初始化线性表 SqList L; Show the menu 显示主界面 五种排序运行后打印结果 五种排序用时的比较，不打印排序后的结果 第 3 页 共 14 页

3.3每个模块的算法设计说明（流程图）

3.3.1气泡排序：

开始 初始变量 i=1，j=1 N i小于L.length Y j小于L.length Y L.elem[j].key大于L.elem[j+1].key Y 交换第j个和第j+1个元素 j++ 结束 第 4 页 共 14 页