各种排序算法时间性能的比较

学号

数据结构课程设计

设计说明书

各种排序算法时间性能的比较

起止日期：2012年1月2日至2012 年1月6日

学生姓名

班级

成绩

指导教师(签字)

电子与信息工程系

2012年1 月2日

天津城市建设学院

课程设计任务书

2011 —2012 学年第一学期

电子与信息工程系专业班级

课程设计名称：数据结构课程设计

设计题目：各种排序算法时间性能的比较

完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周

设计依据、要求及主要内容（可另加附页）：

一、设计依据

[1]《数据结构课程设计指导书》

[2]《数据结构课程设计大纲》

二、设计要求

通过这次设计，要求在数据结构的逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

三、设计内容

1) 问题描述

对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和

归并排序）的时间性能进行比较。

2) 基本要求

(1) 设计并实现上述各种排序算法；

(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；

(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。

3) 设计思想

上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次

数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较

各种排序算法的目的。

直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序

算法中的适当位置插入计数器统计元素的比较次数和移动次数。

【思考题】如果测算每种排序算法所用实际的时间，应如何修改排序算法？

四、参考资料

[1] 王红梅. 数据结构 C++.北京：清华大学出版社，2005.

[2] 王红梅. 数据结构C++实验指导书.北京：清华大学出版社，2005.

[3] 严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社

指导教师（签字）：

教研室主任（签字）：

批准日期：年月日

目录

一、需求分析 (5)

1) 需求描述 (5)

2) 要求 (5)

3) 设计思想 (5)

二、总体设计 (5)

1）程序的系统构造 (5)

2）程序的函数构造及其实现方式 (6)

三、详细设计 (6)

1）数组的录入及其生成 (6)

2）排序算法 (7)

3）记录排序过程 (9)

4）分析并输出结果 (9)

四、调试与测试 (10)

五、关键源程序清单和执行结果 (13)

1）快速排序和堆排序源程序 (13)

2）执行结果概览 (14)

六、参考文献 (15)

一、需求分析

各种排序算法时间性能的比较

1) 需求描述

对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。

2) 要求

(1) 设计并实现上述各种排序算法；

(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；

(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。

3) 设计思想

上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。

二、总体设计

1）程序的系统构造

时间分析是附加功能，时间分析比步数分析更能精确的记录程序的运行过程。

2）程序的函数构造及其实现方式

(1)程序存储结构

所有输入均使用顺序表存储结构。在二叉树的操作中，用 n*2 计算左孩子节点， n*2-1 计算右孩子节点；同理，使用 n/2 计算孩子的父节点。

数组的赋值操作是使用循环对其各项一一赋值。

(2)排序，记录步数

对同一个数组一次进行直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序，统计各个算法中的比较次数和移动次数。

(3)分析结果

对各个算法运行后记录下的总步数进行排序，比较出效率最好的算法和最差第算法。三、详细设计

1）数组的录入及其生成

生成数组后，用循环对数组进行赋值，代码如下：

void initYours( int *test,int n)

{

for( int i = 0; i < n; i++)

{

cin >> test[ i];

}

}

在数组的赋值过程中，必须传入数组长度。然后从test[0..n]依次对数组进行赋值。

在随机数组的生成过程中，使用rand()函数产生伪随机数，用当前时间为随机数的种子，使每次产生的随机数组都不一样。随机数存入数组的代码如下：

void initArr( int *myArr, int n) //初始化数组，将随机数存存入

{

int ran_num;

srand( (unsigned)time( 0 ) );

for(int i = 0; i < n; i++)

{

ran_num = rand()%1000;

myArr[ i] = ran_num;

}

}

种子函数为：srand( (unsigned)time( 0 ) );生成0-1000之间的伪随机数依次存入数组。

2）排序算法

（1）直接插入排序

直接插入排序类似于玩纸牌时整理手中纸牌的过程，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好。

（2）希尔排序

先将整个待排序列分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序时，再对整个记录进行一次直接插入排序。

在本程序的希尔排序中，希尔“逐段分割”的“增量”的计算方法使用：d=d/3+1;d的初始值为n，即数组长度。

（3）冒泡排序

两两比较相邻记录的关键码，如果凡序则交换，直到没有反序记录为止。

具体排序过程为：

1.将整个待排序的记录划分为有序区和无序区，初始状态有序区为空，无序区包所

所有待排记录；

2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得

关键码小的记录向前移动，大大记录向后移动；

3.重复执行2，直到无序区中没有反序的记录。

（4）快速排序

在快速排序中，记录的比较和移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面直接移动到前面，记录移动距离较远，从

而减少了总的移动次数。快速排序的伪代码如下：

1.将i和j分别指向待排序区域的最左和最右侧记录的位置；

2.重复下述过程，知道i=j

a)右侧扫描，直到记录j的关键码小于基准记录的关键码；

b)如果i

c)左侧扫描，知道记录i的关键码大于基准记录的关键码；

d)如果i

3.退出循环，说明i和j指向了基准记录所在位置，返回该位置。

（5）直接选择排序

直接选择排序的实现过程：

1．将整个记录序列划分为有序区和无序区，初始状态有序区为空，无序区含有待排序所有记录；

2．在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序去扩展一个记录，而无序区减少一个记录；

3．不断重复2，知道无序区只剩下一个记录为止。

（6）堆排序

堆排序是直接选择排序的一种改进，改进着眼于如何减少关键码的比较次数。

堆（heap）是具有下列性质的完全二叉树：每个节点的值都小于或者等于其左右孩子的值（小根堆）；或者每个节点的值都大于或等于其左右孩子节点的值（大根堆）。

本次算法，我们采用大根堆排序。先将原数组堆化，然后再进行排序，排序方法入下图所示：

图1

（7）归并排序

本次算法中，用递归实现二路归并。先将待排序列的记录序列分为两个相等的子序列，并分别将这两个子序列用归并的方法进行排序，然后调试一次归并算法Merge，再将这两个有序子序列合并成一个含有全部记录的有序序列。

以下是归并的例子：

图2

3）记录排序过程

在排序函数中，添加变量Ccount和变量Ecount的引用，分别对比较次数和交换次数做比较。当发生一次比较是Ccount自动加1，发生一次交换时Ecount则自动加1。

如下代码，直接插入排序中的Ccount和Ecount引用：

/////////////////////////////////////直接插入排序

void insert_sort( int *a, int n, int &cc, int &ec)

{

int i, j, temp;

for( i = 1; i < n; i++)

{

temp = a[ i];

for( j = i ,/* 测试*/ cc++; j > 0 && temp < a[ j-1]; j-- )

{

a[ j] = a[ j-1]; /* 测试*/ ec++;

}

a[ j] = temp;

}

}

“/*测试*/ cc++”和“/*测试*/ cc++”分别是对Ccount和Ecount的自动加值，每运行一次，则这两个变量自动加1。

4）分析并输出结果

在3）中得到的Ccount和Ecount的值将汇总传入对象数组myseult[7]中，myseult[7]对象数组中包括排序名称和排序过程的记录值。对象的声明如下代码所示：

class Result

{

public:

string sortName;

double value;

}myresult[ 7]; //结果存储

存入数据后再对数据进行排序分析并输出排序结果，分析结果函数如下：void analysis_result()

{

initResName(); //初始化分析结果名

int i, j;

Result temp; //对结果排序

for( i = 1; i < 7; i++)

{

temp = myresult[ i];

for( j = i; j > 0 && temp.value < myresult[ j-1].value; j--)

{

myresult[ j] = myresult[ j-1];

}

myresult[ j] = temp;

}

cout << "analysis result:" << endl;

for( i = 0; i < 7; i++)

{

cout << myresult[ i].sortName << "(" << myresult[ i].value << ")";

if( i < 6 ) cout << " < ";

}

cout << endl;

cout << "best:" << myresult[ 0].sortName << endl;

cout << "bad: " << myresult[ 6].sortName << endl;

cout << endl << endl << endl << endl;

}

四、调试与测试

1．程序主界面

图 2

2．对数组进行正序排序

图3

3.对数组进行逆序排序

图4

4.输出性能分析结果（对100个随机数数组进行分析）

图5

五、关键源程序清单和执行结果

1）快速排序和堆排序源程序

////////////////////////////////////快速排序

void quick_sort( int *a, int low, int high)

{

int i = low, j = high;

int temp = a[ low];

if( low >= high) return;

while( i != j)

{

while( i < j && a[ j] >= temp)

j--;

a[ i] = a[ j];

while( i < j && a[ i] <= temp)

i++;

a[ j] = a[ i];

}

a[ i] = temp;

quick_sort( a, low, i - 1); //递归

quick_sort( a, i + 1, high);

}

////////////////////////////////////堆排序

void MaxHeapify( int *a, int i, int n) //此处i重开始，因此一下所有相关下标-1 {

int lc = i*2-1, rc = i*2;

int largest; //largest，最大数下标

int temp;

if( lc < n && a[ lc] > a [ i-1])

{

largest = lc;

} else{

largest = i-1;

}

if( rc < n && a[ rc] > a[largest])

{

largest = rc;

}

if( largest != i-1)

{

temp = a[ i-1];

a[ i-1] = a[ largest];

a[ largest] = temp;

largest++; //恢复i值，即i+1

MaxHeapify( a, largest, n);

}

}

void BuildMaxHeap( int *a, int n)

{

for( int i = n/2; i > 0; i--)

{

MaxHeapify( a, i, n);

}

}

void heap_sort( int *a, int n)

{

int i, temp;

BuildMaxHeap( a, n);

for( i = n-1; i > 0 ; i--)

{

temp = a[ 0];

a[ 0] = a[ i];

a[ i] = temp;

MaxHeapify( a, 1, i); //将a[0] 下沉}

}

2）执行结果概览

图6

图7

六、参考文献

1．王红梅．数据结构．清华大学出版社

2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社