内容发布更新时间 : 2024/12/28 10:52:00星期一 下面是文章的全部内容请认真阅读。

深 圳 大 学 实 验 报 告

课程名称： 算法分析与复杂性理论

实验项目名称： 实验一 排序算法性能分析

学院： 计算机与软件学院

专业： 软件工程

指导教师： 杨烜

报告人：赖辉 学号： 班级： 软工学术型

实验时间： 2015-10-15

实验报告提交时间： 2015-11-24

教务部制

一．实验目的

1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理

2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

二．实验步骤与结果

实验总体思路：

根据实验要求，需要用while循环控制用户选择相应算法(选择通过switch实现)或者选择输入0跳出while循环，退出程序。Switch中选择相应的算法后需要通过一个for(int j=0;j<5;j++)循环更改数组大小MAX的值(MAX *= 10)，从而控制输入不同问题规模的耗时。再通过一个for(int i=0;i<20;i++)循环控制20组随机数组。为了使得程序输出更加直观，部分数据后面没有输出。相应结果和过程如下所示（代码和结果如下图所示）。

各排序算法的实现及实验结果：

1、随机数产生 代码1：

srand((unsigned)time(NULL)); For i=0 to 19

randNum(MAX,array);

当问题规模较小时，生成随机函数randNum()在for循环下运行时间短，每次产生的随机数组都是一样的，将srand((unsigned)time(NULL))语句放在for循环外面，就产生了20组不同的随机数组。

图1、产生20组随机数组

2、选择排序 代码2：

for i=0 to n-2

min=i

for j= i+1 to n-1

if ele[min]>ele[j] min=j swap(ele[i],ele[min]) //交换元素

图2、选择排序在不同数据规模下排序所消耗的时间 3、冒泡排序 代码3： for i= 0 to n-1

for j=0 to n-1-i

if a[j]>a[j+1]

swap(a[j],a[j+1]) //交换