数据结构课程设计--排序算法比较.docx

;1

EASTCHINAINSTITUTEOFTECHNOLOGY

《数据结构与算法设计》课程设计报告

题目：排序算法比较

学生姓名：

学号：201120181805

班级：1121822

指导教师：··清

2013年1月10日

’2

目录

需求分析 3

总体设计 4

详细设计 5

类的设计 5

现实部分 8

随机数赋值 8

结果输出 8

直接插入排序 9

冒泡排序 10

选择排序 11

快速排序 13

堆排序 15

二路归并排序 18

程序测试 21

总结 25

需求分析

本程序主要为了实现对各排序算法的性能比较。主要包括对直接插入排序，冒泡排序，选择排序，快速排序，堆排序二路归并排序六种排序算法在时间复杂度上的性能比较。基于此目的需要设定一个顺序表来产生一组数据，本程序用了一个长度为30000的longint型数组并用了以时间为随机种子产生了一组数

组。用六个模块来实现各种排序功能并在各模块中完成计算排序

’3

所用的时间。并用一个数组保存各种排序所用的时间。为了比较各种排序的在时间上的优劣性将各个排序所用的时间进行比较

并输出结果!

二.总体设计

开始

设定long数组

Switch结构

’4

二路归

二路归并排

选择排序

冒泡排序

直接插入排

堆排序

快速排序

序序

序

进行二路归并排序进避值髏海排腓序进行堆排序进行题耀排序进行选择排序进行快速排序

进行二路归并排序

进避值髏海排腓序

进行堆排序

保存所需时间保存所需时间保存所需时间保存所需时间保存所需时间保存所需时间

获得所有排序所花费的时间(包括未switch结构中未被选中的排序)

对所有排序的时间进行从小到大的排序并输出结果

结束

三.详细设计

1.类的设计

本程序功能只是为了比较各种排序算法在时间上的优劣。所以可

以用一个类来完成的有的操作，固本程序只需定义一个类。

为实现本程序功能定义一个类其中包括了一个长度300000的数组。并且为了实现各种排序功能应当设计功能函数分别实现各种类型

的排序和排序后的结果。以下对这个类进行详细说明。

;s

,6

类名：:

sortrather

数据成员：

longinta[N]其中N为一个全局常量其值为30000,该成员用来保

存一个用于保存一组数据用于排序。

Longinttime[6]该数组用于保存各种排序所用的时间，以便对种种

排序所用时间进行比较。

成员函数：

1.voidpubction()

实现功能：

本函数的的作用是给数据成员a[N]进行随机赋值。

实现算法：用系统时间作为随机种子。再将随机函数对90000的

取余赋给。a[N].

2.print()

实现功能：

将a[N]的前30个元素输出。

实现算法：将数组元素一个一个的输出。

3.voidinsertsort()

实现功能：

以直接插入排序算法完成对数组a的直接插入排序。

实现算法：

以当前元素以基准元素，将后面的元素与其进行比较。如果比

9

7

当前元素大则直接插到当前元素后面。否则把当前元素后移并置

当前元素为前一个元素。重复此步骤。

4voidbubblesort()

实现功能：

以冒泡的方式对数组a[N]进行排序。

实现算法：从第N-1个数开始与前一个数比较使之小的在的前大的在后，直到第1个数，这样便找到了最小的用同样的方法找

到第二小的数·

3.voidselectsort(longinta[],longintn)

实现功能：

以选择排序的方法完成对a[N]的排序。

实现算法：

依次取数组a[N]中的第一个、第二个……到第a[N]个，与数组中它所在位置后的其它元素进行比较并使a[1],a[2],……a[N]取余下元素

的最小值。

4.voidquick(longinta[],longintleft,longintright)

实现功能：

用快递排序的方法来实现对a[N]从小到大的排序

实现算法：

先取a[1]作为基准点从a[-1]开始依次与基准点比较若a[1]大于其中的某个数则交换a[1]与这个数的值。并以该数为基准点从

a[2]开始从复以上步骤真以基准点为界两边的