数据结构各种排序算法的时间性能

HUNAN UNIVERSITY

课程实习报告

题 目： 排序算法的时间性能

学生姓名

学生学号

专业班级

指导老师 李晓鸿 完 成 日 期

设计一组实验来比较下列排序算法的时间性能

快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求

(1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。

(2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。

(3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。

(5)要给出实验的方案及其分析。 说明

本题重点在以下几个方面：

理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。

一、需求分析

(1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比

较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数

(2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和

比较次数。

(3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机

数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略

二、概要设计

1.抽象数据类型

ADT List

数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系 R1＝{ |ai-1 ,ai∈D, i=2,...,n } 基本操作 virtual void clear() = 0;

bool insert(const Elem&) = 0; bool append(const Elem&) = 0; lbool remove(Elem&) = 0;

void setStart() = 0;

void setEnd() = 0; void prev() = 0; void next() = 0;

int leftLength() const = 0; int rightLength() const = 0; bool setPos(int pos) = 0;

bool getValue(Elem&) const = 0; void print() const = 0;

2.程序的流程

（1） 输入模块：输入要排序的数的数量n

（2） 处理模块：系统产生n个随机数，对随机数进行排序 （3） 输出模块：将排序的结果输出

3.算法的基本思想

1、 随机数的产生：利用srand()产生随机数。

2、 快速排序：选定一记录R，将所有其他记录关键字k’与记录R的关键字

k比较, 若 k’k 则将记录换至R之后，继续对R前后两部分记录进行快速排序，直至排序范围为1

3、 插入排序：逐个处理待排序的记录，每个新记录与前面已排序的子序列

进行比较，将它插入到子序列中正确的位置

4、 冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地

方为止。

5、 归并排序：将两个或者多个有序表归并成一个有序表

6、 堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大

元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数组。

三、详细设计

（1）产生随机数：直接调用函数srand(),以时间作为随机种子进行选择，并把随机数装入数组中

unsigned long int *Sort::setRan(unsigned long int num){ unsigned long int *ra; ra=(unsigned long int*)malloc(num*sizeof(unsigned long int)); srand(time(NULL)); for(unsigned long int m=0;m

（2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当low,high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归快速排序，直到范围为1结束。

int partition(int a[],int low,int high){//快速排序中的一趟

int pivotkey; //作为枢轴来使用 pivotkey=a[low]; while(low

while(low=pivotkey) --high;

a[low]=a[high];

while(low

a[high]=a[low]; }

a[low]=pivotkey; return low; }

void qsort(int a[],int low,int high){//快速排序的递归形式 int pivotloc;