五种排序算法分析

深 圳 大 学 实 验 报 告

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

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

学院: 计算机与软件学院

专业: 软件工程

指导教师: 杨烜

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

实验时间: 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]) //交换

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4