数据结构（C语言）各种排序算法性能比较

信安科技大学布新学浣毕业论文数据结构（C语言）各种排序算法性能比较系_ _ _ _ _ _ _ _ _ 机电信息学院_ _ _ _ _ _ _ _ _ _ _ _ _ _ _专 业 计算机科学与技术姓 名 段大志班级 计 科 1001 学 号 1001020110指导 教 师 田 莘 职称讲师设计时 rn 2011.1.1-2012.1.8_摘要排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本毕业论文对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序以及堆排序算法进行比较。我们设置待排序表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种,对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的比较次数和关键字的移动次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序虽然交换次数很少，但比较次数较多。关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序;引言人类已进入2 1世纪,科学技术突飞猛进,经济知识和信息产业初见端倪,特别是信息技术和网络技术的讯速发展和广泛应用，对社会的政治，经济，军事，文化等领域产生越来越深刻的影响，也正在改变人们的工作，生活学习，交流方式。信息的获取，处理,交流和应用能力，已经成为人们最重要的能力之一。在不久的将来知识经济将占世界经济发展的主导地位，国家综合国力和国际竞争能力越来越取决于教育发展,科学技术和知识创新的水平，教育在经济和社会发展过程中将呈现出越来越突出的重要作用。1 9 6 8年美国唐欧克努特开创了数据机构的最初体系。现在，数据结构是一们介于数学、计算机硬件和计算机软件三者之间的核心课程。随 着In t e r n e t的出现，网络正在改变整个世界，由 于In t e r n e t具有传播信息容量极大、形态多样、迅速方便、全球覆盖、自由和交互的特点，已经发展成为新的传播媒体，而将教育和网络相结合，将会更好的推动教育的发展。现在不仅很多大学和众多企业部门都已经建立了自己的网站，而且个人网站也如雨后春笋般大量的出现，通过计算机网络实现宣传、交流及资源的整合学好数据结构的基础，会对编程设计有进一步的提高，使编程能力上一个台阶，从而使自己学习和开发软件的能力进一步提高！。目录摘要.I引言.II第一章绪论.11.1 研究的背景及意义.11.2 研究现状.11.3 本文主要内容.1第二章排序基本算法.32.1直接插入排序.32.1.1基本原理.32.1.2排序过程.32.1.3时间复杂度分析.32.2直接选择排序.32.2.1基本原理.32.2.2 排序过程.42.2.3 时间复杂度分析.42.3冒泡排序.42.3.1基本原理.42.3.2排序过程.52.3.3时间复杂度分析.62.4 SHELL 排序.62.4.1基本原理.62.4.2排序过程.62.4.3时间复杂度分.72.5堆排序.72.5.1基本原理.72.5.2排序过程.72.5.3时间复杂度分析.112.6快速排序.112.6.1基本原理.112.6.2排序过程1.22.6.3时间复杂度分析.13第三章系统设计.133.1数据定义.133.2程序流程图.133.3数据结构设计.133.4系统的模块划分及模块功能实现.143.4.1系统模块划分.143.4.2各排序模块功能实现.14第四章运行与测试.24第五章总结.27参考文献.28致谢.29第一章绪论1.1 研究的背景及意义排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排序算法是在整个计算机科学与技术领域上广泛被使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。本人在研究各种算法的过程中，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行过程，目的有以下五个方面：做算法的对比研究，培养研究能力；开发一个独立的软件，培养程序设计和软件开发能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；为教学服务，研 究 结 果 对 抽 象 的 算法与数据结构 的教学有一定的辅助作用。排序是计算机科学中最重要的研究问题之一，它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。1.2 研究现状随着计算机技术的日益发展，其应用早已不局限于简单的数值运算。而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。近来国内外专家学者们对排序算法又有了新的研究和发现。例如：我国山东大学的张峰和张金屯两位教授共同研究了我国植被数量分类和排序研究进 展 这课题。很值得有关部门去学习和研究。1.3 本文主要内容排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果排序中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序六类。本文编写一个程序对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序及堆排序这几种内部排序算法进行比较，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图表数据汇总，以便对这些内部排序算法进行性能分析。第二章排序基本算法2.1 直接插入排序2.1.1 基本原理假设待排序的n个记录 RO,R1,，Rn 顺序存放在数组中，直接插入法在插入记录Ri(i=l,2,，n-1)时,记录被划分为两个区间RO,Ri-被和Ri+1,个T,其中,前一个子区间已经排好序，后个子区间是当前未排序的部分，将关键码K i 与 K iT K i-2,，K 0 依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i T个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i T趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2.1.2 排序过程初始数据：1 0 3 2 5 2 0 8第趟：3 1 0 2 5 2 0 8 (将前两个数据排序)第二趟：3 1 0 2 5 2 0 8 (将 2 5 放入前面数据中的适当位置)第三趟：3 1 0 2 0 2 5 8 (将 2 0 放入适当的位置)2.1.3 时间复杂度分析直接插入排序算法必须进行n-1 趟。最好情况下，即初始序列有序，执行n-1 趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1),移动元素次数是2 (n-1)。因此最好情况下的时间复杂度就是0(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为0(n 2)。2.2直接选择排序2.2.1 基本原理待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的，2-1 个记录中再选出关键码最小的记录与第二个记录交换；如此，第 i 趟，则 从 第 i 个记录开始的n -i+1个记录中选出关键码最小的记录与第i 个记录交换，直到所有记录排好序。2.2.2 排序过程初始数据 4 9 3 8 6 5 9 7 7 6 1 3 2 7 4 9 第一趟排序后1 3 3 8 6 5 9 7 7 6 4 9 2 7 4 9 第二趟排序后1 3 2 7 6 5 9 7 7 6 4 9 3 8 4 9 第三趟排序后1 3 2 7 3 8 9 7 7 6 4 9 6 5 4 9 第四趟排序后1 3 2 7 3 8 4 9 4 9 9 7 6 5 7 6 第五趟排序后1 3 2 7 3 8 4 9 4 9 9 7 9 7 7 6 第六趟排序后1 3 2 7 3 8 4 9 4 9 7 6 7 6 9 7 第七趟排序后1 3 2 7 3 8 4 9 4 9 7 6 7 6 9 7 最后排序结果1 3 2 7 3 8 4 9 4 97 6 7 6 9 72.2.3 时间复杂度分析该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1 次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为0(n 2)o2.3冒泡排序2.3.1基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列(I O r i n T )中从前往后进行两个相邻元素的比较，若后者小，则交换，比较nT次；第一趟排序结束，最大元素被交换到I n T 中，下一趟只需在子序列(I 0 n n-2)中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组J1 n 垂直排列,每个记录Ji看作是重量为Ji.k e y的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。2.3.2 排序过程将被排序的记录数组R 1 n垂直排列，每个记录R i 看作是重量为R i .k e y的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。(1)初始R l.n为无序区。(2)第一趟扫描从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R n,R n-1 )(R n-1 ,R n-2 ),(R 2 ,R l )；对于每对气泡(R j+1 ，R j )，若 R j+l .k e yR j .k e y,则交换 R j+1 和 R j 的内容。第一趟扫描完毕时，最轻”的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R l 上。(3)第二趟扫描扫 描R 2,n。扫描完毕时，次轻”的气泡飘浮到R 2 的位置上，最后，经过n-1趟扫描可得到有序区R 1 n。第i趟扫描时,R 1 i T和R i n分别为当前的有序区和无序区。扫描仍是从底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R i 上，结果是R 1 i 变为新的有序区。初始数据7 6 3 2 4 6 8 0 5 5 4 6*第一轮：第一趟排序后3 2 7 6 4 6 8 0 5 5 4 6*第二趟排序后第三趟排序后第四趟排序后3 2 4 6 7 63 2 4 6 7 63 2 4 6 7 68 0 5 5 4 6*8 0 5 5 4 6*5 5 8 0 4 6*第五趟排序后 3 2 4 6 7 6 5 5 4 6*8 0第二轮排序结果3 2 4 6 5 5 4 6*7 6 8 0第三轮排序结果3 2 4 6 4 6 5 5 7 6 8 0第四轮排序结果