1 / 8
《数据结构与算法》实验报告
学生姓名 院(系) 计算机科学与技术
学 号 专 业
实验时间 实验地点
实验项目 实验 5:排序算法实验比较
实验目的:将课程的基本原理、技术和方法与实际应用相结合,训练和提高
学生组织、存储和处理信息的能力,以及复杂问题的数据结构设计能力和程序设
计能力,培养软件设计与开发所需要的实践能力。
实验要求:灵活运用基本的数据结构和算法知识,对实际问题进行分析和抽
象;结合程序设计的一般过程和方法为实际问题设计数据结构和有效算法;用高
级语言对数据结构和算法进行编程实现、调试,测试其正确性和有效性。
实验内容:排序算法的实现与实验比较
实现一组经典的排序算法,通过实验数据的设计,考察不同规模和分布的
数据对排序算法运行时间影响的规律,验证理论分析结果的正确性。
1. 实现以下三组排序方法中的一组排序算法:
(1)冒泡排序和快速排序;
(2)插入排序和希尔排序;
(3)选择排序和堆排序。
2. 产生不同规模和分布的数据,以“图或表”的方式给出输入规模和分布对排
序方法运行时间变化趋势的影响(画出 T(n)的曲线)。并与理论分析结果比较。
3. 将上述“图或表”采用图片等形式贴在实验报告中,与作适当分析或说明。
数据结构定义:
int arr[] /* 用于排序的数组 */
算法设计与分析(要求画出核心内容的程序流程图):
1. 冒泡排序 Bubble Sort
冒泡排序基本思想是对所有的元素进行遍历,每相邻的两个元素比较大
小,较小元素交换到前面,所有元素遍历完成后即排序完成。冒泡排序稳定
但是时间消耗很大。时间复杂度为O(n
2
).
评论0