请下载论文,论文为word格式,只上传部分查看,如果需要此参考论文,请点击-下载论文,下载资料。
摘要
排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本毕业论文对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序以及堆排序算法进行比较。
我们设置待排序表的元素为整数,用不同的测试数据做测试比较,长度取固定的三种,对象由随机数生成,无需人工干预来选择或者输入数据。比较的指标为关键字的比较次数和关键字的移动次数。
经过比较可以看到,当规模不断增加时,各种算法之间的差别是很大的。这六种算法中,快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排序和快速排序差不多,属于同一个数量级。直接选择排序虽然交换次数很少,但比较次数较多。
关键字:直接插入排序;直接选择排序;起泡排序;Shell排序;快速排序;堆排序;
目录
摘要2
第一章 绪论3
1.1 研究的背景及意义3
1.2 研究现状3
1.3 本文主要内容4
第二章 排序基本算法5
2.1 直接插入排序5
2.1.1基本原理5
2.1.2排序过程5
2.1.3时间复杂度分析5
2.2 直接选择排序6
2.2.1基本原理6
2.2.2 排序过程6
2.2.3 时间复杂度分析6
2.3冒泡排序7
2.3.1基本原理7
2.3.2排序过程7
2.3.3 时间复杂度分析8
2.4 Shell排序8
2.4.1基本原理8
2.4.2排序过程9
2.4.3时间复杂度分析9
2.5堆排序9
2.5.1基本原理9
2.5.2排序过程10
2.5.3时间复杂度分析13
2.6快速排序13
2.6.1基本原理13
2.6.2排序过程14
2.6.3时间复杂度分析15
3.1数据定义16
3.2 程序流程图16
3.3 数据结构设计17
3.4 系统的模块划分及模块功能实现17
3.4.1系统模块划分17
3.4.2各排序模块功能实现18
第四章 运行与测试29
第五章 总结31
致谢32
参考文献33