深 圳 大 学 实 验 报 告
课程名称： 算法分析与复杂性理论
实验项目名称： 实验一 排序算法性能分析
学院： 计算机与软件学院
专业： 软件工程
指导教师： 杨烜
报告人：赖辉 学号： 班级： 软工学术型
实验时间： 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]) //交换