算法与复杂性理论实验基本排序题稿.docx

深 圳 大 学 实 验 报 告 课程名称： 算法设计与分析 实验名称： 多种排序算法的算法实现及性能比较 学院： 计算机与软件学院 专业： 计算机科学与技术 报告人： 张健哲 学号： 2013150372 班级： 3 同组人： 无 指导教师： 李炎然 实验时间： 2015/3/25——2015/4/8 实验报告提交时间： 2015/4/8 教务处制 一．实验目的 1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。 二．实验步骤与结果 实验总体思路： 利用switch结构来选择实验所要用的排序算法，每一种排序都用相同的计算运行时间的代码，不同的算法就在算法实现部分进行改动（如下代码1至5所示）。不断的改变数据规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。最后输出在不同排序算法下，不同的数据规模的20次实验样本和平均用时（如下图1至5所示）。 各排序算法的实现及实验结果： （注1：以下代码全部为伪代码，具体代码实现请参照程序中的代码） （注2：图中显示的时间单位均为毫秒，图中“排序所花时间”一项为平均消耗时间，平均消耗时间结果以20组样本计算平均值后取整得到（并非四舍五入）。） 1、选择排序 代码1： 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]) //交换 图1、选择排序在不同数据规模下排序所消耗的时间 2、冒泡排序 代码2： 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]) //交换 图2、冒泡排序在不同数据规模下排序所消耗的时间 3、合并排序 代码3： Merge(ele[1...n],left,right) middle=(left+right)/2 if right1eft+1 Merge(ele,left,middle) Merge(ele,middle+1,right) l←left r←right i←left while l=middler=right //两组分别一一比较，数据小的放入ele if ele[l]=ele[r] t[i++]←ele[l++] else t[i++]←ele[r++] while lmiddler=r //只剩一组还有剩余的时，将剩下的按顺序放入 ele[i++]=s[r++] while l=middle rright ele[i++]=s[l++]; 图3、合并排序在不同数据规模下排序所消耗的时间 4、快速排序 代码4： quick(ele[0...n-1],left,right) if lr l←left r←right x←ele[l]; while lr while lr x=ele[r] //找到一个比x小的数之后交换到前面的部分 r-- if lr ele[l]←ele[r] l++ while lr xele[l] //与上面相反 ll++ if lr ele[r]←ele[l] r-- ele[l]←x; quick(ele,left,l-1) // 递归调用 quick(ele,l+1,right) 图4、快速排序在不同数据规模下排序所消耗的时间 5、插入排序 代码5： for i=1→n-1 if ele[i]ele[i-1] temp=ele[i] for j= i-1 to 0 ele[j]temp ele[j+1]←ele[j] ele[j+1]←temp 图5、插入排序在不同数据规模下排序所消耗的时间 三．实验分析 选择排序： 图6、由图1数据整合而成的折线图 为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧