毕业论文各种排序算法性能比较系专业姓名班级学号指导教师职称设计时间目录摘要 (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)第三章系统设计 (16)3.1数据定义 (16)3.2 程序流程图 (16)3.3 数据结构设计 (17)3.4 系统的模块划分及模块功能实现 (17)3.4.1系统模块划分 (17)3.4.2各排序模块功能实现 (18)第四章运行与测试 (29)第五章总结 (31)致谢 (32)参考文献 (33)江苏信息职业技术学院毕业论文摘要排序算法是数据结构这门课程核心内容之一。
它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。
学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。
本毕业论文对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序以及堆排序算法进行比较。
我们设置待排序表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。
比较的指标为关键字的比较次数和关键字的移动次数。
经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。
这六种算法中，快速排序比较和移动的次数是最少的。
也是最快的一种排序方法。
堆排序和快速排序差不多，属于同一个数量级。
直接选择排序虽然交换次数很少，但比较次数较多。
关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序；第一章绪论1.1 研究的背景及意义排序是计算机程序设计中的一种重要操作。
它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。
排序算法是在整个计算机科学与技术领域上广泛被使用的术语。
排序算法是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
本人在研究各种算法的过程中，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行过程，目的有以下五个方面：做算法的对比研究，培养研究能力；开发一个独立的软件，培养程序设计和软件开发能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；为教学服务，研究结果对抽象的《算法与数据结构》的教学有一定的辅助作用。
排序是计算机科学中最重要的研究问题之一, 它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。
由于它固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。
其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。
1.2 研究现状随着计算机技术的日益发展，其应用早已不局限于简单的数值运算。
而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。
排序算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。
近来国内外专家学者们对排序算法又有了新的研究和发现。
例如：我国山东大学的张峰和张金屯两位教授共同研究了《我国植被数量分类和排序研究进展》这课题。
很值得有关部门去学习和研究。
江苏信息职业技术学院毕业论文1.3 本文主要内容排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。
如果排序中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序六类。
本文编写一个程序对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序及堆排序这几种内部排序算法进行比较，用不同的测试数据做测试比较。
比较的指标为关键字的比较次数和关键字的移动次数。
最后用图表数据汇总，以便对这些内部排序算法进行性能分析。
第二章排序基本算法2.1 直接插入排序2.1.1基本原理假设待排序的n个记录{R0，R1，…，Rn}顺序存放在数组中，直接插入法在插入记录Ri(i=1，2，…，n-1)时，记录被划分为两个区间[R0,Ri-1]和[Ri+1,Rn-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
2.1.2排序过程初始数据：10 3 25 20 8第一趟：[ 3 10 ] 25 20 8 （将前两个数据排序）第二趟：[ 3 10 25] 20 8 （将25 放入前面数据中的适当位置）第三趟：[ 3 10 20 25 ] 8 （将20 放入适当的位置）第四趟：[ 3 8 10 20 25 ] （将8 放入适当的位置）2.1.3时间复杂度分析直接插入排序算法必须进行n-1趟。
最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。
因此最好情况下的时间复杂度就是O(n)。
最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。
江苏信息职业技术学院毕业论文2.2 直接选择排序2.2.1基本原理待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。
第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的，2 -1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i 趟，则从第i个记录开始的n - i + l个记录中选出关键码最小的记录与第i 个记录交换，直到所有记录排好序。
2.2.2 排序过程初始数据[49 38 65 97 76 13 27 49]第一趟排序后13 ［38 65 97 76 49 27 49]第二趟排序后13 27 ［65 97 76 49 38 49]第三趟排序后13 27 38 [97 76 49 65 49]第四趟排序后13 27 38 49 [49 97 65 76]第五趟排序后13 27 38 49 49 [97 97 76]第六趟排序后13 27 38 49 49 76 [76 97]第七趟排序后13 27 38 49 49 76 76 [ 97]最后排序结果13 27 38 49 49 76 76 972.2.3 时间复杂度分析该算法运行时间与元素的初始排列无关。
不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)。
2.3冒泡排序2.3.1基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。
经过一趟起泡后，关键词大的必须移到最后。
按照这种方式进行第一趟在序列（I[0]~I[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。
将被排序的记录数组J[1…n]垂直排列，每个记录J[i]看作是重量为J[i].key的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。
如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。
2.3.2排序过程将被排序的记录数组R[1 …n]垂直排列，每个记录R[i]看作是重量为R[i].key 的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。
如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始R[1..n]为无序区。
（2）第一趟扫描从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。
即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
（3）第二趟扫描扫描R[2,…,n]。
扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……,最后，经过n-1 趟扫描可得到有序区R[1…n]。
江苏信息职业技术学院毕业论文第i趟扫描时,R[1…i-1]和R[i…n]分别为当前的有序区和无序区。
扫描仍是从底部向上直至该区顶部。
扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1…i]变为新的有序区。
初始数据76 32 46 80 55 46*第一轮：第一趟排序后32 76 46 80 55 46*第二趟排序后32 46 76 80 55 46*第三趟排序后32 46 76 80 55 46*第四趟排序后32 46 76 55 80 46*第五趟排序后32 46 76 55 46* 80第二轮排序结果32 46 55 46* 76 80第三轮排序结果32 46 46 55 76 80第四轮排序结果32 46 46* 55 76 80第五轮排序结果32 46 46* 55 76 802.3.3 时间复杂度分析当原始数据正向有序时，冒泡排序出现最好情况。