各种排序算法性能比较毕业论文.doc

毕业论文 各种排序算法性能比较 系 专业 姓名 班级 学号 指导教师 职称 设计时间 目录摘要2第一章 绪论31.1 研究的背景及意义31.2 研究现状31.3 本文主要内容4第二章 排序基本算法52.1 直接插入排序52.1.1基本原理52.1.2排序过程52.1.3时间复杂度分析52.2 直接选择排序62.2.1基本原理62.2.2 排序过程62.2.3 时间复杂度分析62.3冒泡排序72.3.1基本原理72.3.2排序过程72.3.3 时间复杂度分析82.4 Shell排序82.4.1基本原理82.4.2排序过程92.4.3时间复杂度分析92.5堆排序92.5.1基本原理92.5.2排序过程102.5.3时间复杂度分析132.6快速排序132.6.1基本原理132.6.2排序过程142.6.3时间复杂度分析15第三章 系统设计163.1数据定义163.2 程序流程图163.3 数据结构设计173.4 系统的模块划分及模块功能实现173.4.1系统模块划分173.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基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列（I0In-1）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到In-1中，下一趟只需在子序列（I0In-2）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组J1 n垂直排列，每个记录Ji看作是重量为Ji.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。2.3.2排序过程将被排序的记录数组R1 n垂直排列，每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。（1）初始 R1.n为无序区。（2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；对于每对气泡(Rj+1，Rj)，若Rj+1.keyRj.key，则交换Rj+1和Rj的内容。 第一趟扫描完毕时，最轻的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R1上。（3）第二趟扫描 扫描R2,n。扫描完毕时，次轻的气泡飘浮到R2的位置上,最后，经过n-1趟扫描可得到有序区R1n。 第i趟扫描时,R1i-1和Rin分别为当前的有序区和无序区。扫描仍是从底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置Ri上，结果是R1i变为新的有序区。初始数据 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 80 2.3.3 时间复杂度分析当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O(n2)。2.4 Shell排序2.4.1基本原理Shell排序又称缩小增量排序,Shell排序法是以创建者Donald Shell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2d1重复上诉分组和排序工作；直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入，直到dt=1，即所有记录放在一组中为止。2.4.2排序过程先取一个正整数d1n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。 初始数据：49 38 65 97 76 13 27 48 55 04 一趟结果(d=5):13 27 48 55 04 49 38 65 97 76 二趟结果(d=3): 13 04 48 38 27 49 55 65 97 76 三趟结果(d=1): 04 13 27 38 48 49 55 65 76 972.4.3时间复杂度分析希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为o(n2)。2.5堆排序2.5.1基本原理堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程，直到堆中只剩一个元素,n个关键字序列 kl , k2 ， ， kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）: ( l) ki= k2i 且 ki= k2i 且 ki=k2i+1。若将此序列所存储的向量 R 1n看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树:树中非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。注意： 堆中任一子树亦是堆。 以上讨论的堆实际上是二叉堆，类似地可定义 k 叉堆。2.5.2排序过程堆排序是一树形选择排序。堆排序的特点是：在排序过程中，将 R 1 n 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之问的内在关系，在当前无序中选抒关键字最大（或最小）的记录。下面将从实际数据中演示其排序中的各个操作。原始数组： 22 53 72 11 34 44 11 15 28 3 10 65 第一步，从树顶到树叶把数填充进入，建立堆。红色为下一次交换的两个数（序列）。使记录递增有序，进一步排序。第一次交换：第二次交换：第三次交换：第四次交换：第五次交换：第六次交换：第七次交换：第八次交换：第九次交换：全程交换完成，得到最小值为 3 并且输出它。从序列中删除 3 ，重新建立堆。以次循环，直到全部输出完成为止。2.5.3时间复杂度分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。2.6快速排序2.6.1基本原理首先我们选择一个中间值 middle （程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该排序码的记录移到右边，中级放所选记录，为一趟快速排序。然后对前后两个子序列分别重新上述过程，直到所有记录都排好序。对任意给定的序列中某个元素，经过一趟排序后，将原序列分割成两个子序列(Rp(0),Rp(1),Rp(s-1)和(Rp(s+1),Rp(s+2),Rp(n-1)，其中前一个子序列中的所有元素的关键词均小于或等于该元素的关键词值Kp(s)，后一个子序列中元素的关键词均大于或等于Kp(s)。称该元素Rp(s)为分割元素，子序列(Rp(0),Rp(1),Rp(s-1)为其低端序列，(Rp(0),Rp(1),Rp(s-1)为其高端序列。很明显，以后只需对低端和高端序列分别进行快速排序，直到子序列为空或只有一个元素时结束，最后得到有序序列。总之，每趟使表的第一个元素放在适当位置，将表两分，再对子表进行同样的递归划分，直至划分的子表长度为1。2.6.2排序过程假设要排序的数组是A1AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I=1，J=N； 2）以第一个数组元素作为关键数据，赋值给X，即X=A1； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J； 例如：待排序的数组A的值分别是： A1 A2 A3 A4 A5 A6 A7： 49 38 65 97 76 13 27进行第一次交换后：27 38 65 97 76 13 49 进行第二次交换后: 27 38 49 97 76 13 65进行第三次交换后：27 38 13 97 76 49 65进行第四次交换后：27 38 13 49 76 97 65此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全在49的后面，所以小于49的数全部在49的前面。快速排序就是递归调用此过程在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如下所示：初始状态: 49 38 65 97 76 13 27 进行一次快速排序之后划分为:27 38 13 49 76 97 65分别对前后两部分进行快速排序: 13 27 38;97 76 652.6.3时间复杂度分析如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。第三章 系统设计3.1数据定义输入数据：由于大多数排序算法的时间开销主要是关键字之间的比较和记录的移动，算法的执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。所以对于输入数据，我们采用由用户输入记录的个数（以关键字的数目分别为20，100，500为例），测试数据由随机数产生器生成。输出数据：产生的随机数分别用直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。3.2 程序流程图主程序产生1组随机数起泡排序Shell排序快速排序直接选择排序堆排序记录关键字的比较次数和移动次数将随机数保存在数组中循环20次输出关键字的比较次数、移动次数的平均值直接插入排序 图3.1 程序流程图3.3 数据结构设计本程序中，考虑的内容就是待排序对象，排序的依据是关键字之间的大小比较，故在每个节点的类型定义中，至少得包含关键字key一项。不失一般性，这里就使用关键词这一项，其他都省略，具体应用加上其他数据项即可。被排序对象是由一个个节点够成，一个排序对象包含一系列指向一串节点的指针，排序对象的长度。本程序功能简单。typedef structint key; /*关键字*/RecordNode; /*排序节点的类型*/typedef structRecordNode *record;int n; /*排序对象的大小*/SortObject; /*排序节点的类型*/3.4 系统的模块划分及模块功能实现3.4.1系统模块划分MainInsertSortSelectSortBubbleSortSortMethodQuickSortHeapSortShellSortOutputQuick图3.2 系统模块划分图3.4.2各排序模块功能实现A直接插入排序void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)int i,j;RecordNode temp; SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf(OverFollow!);getchar();exit(1);for(i=0;in;i+)/* 复制数组*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=1;in;i+) temp=pvector-recordi; (*exchange)+; j=i-1; while(temp.keyrecordj.key)&(j=0) (*compare)+; (*exchange)+; pvector-recordj+1=pvector-recordj; j-; if(j!=(i-1) pvector-recordj+1=temp; (*exchange)+; free(pvector);当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。B.直接选择排序void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,j,k; RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!);getchar();exit(1); for(i=0;in;i+)/*复制数组*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) (*compare)+; if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) temp=pvector-recordi; pvector-recordi=pvector-recordk; pvector-recordk=temp; ( *exchange)+=3; free(pvector);选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.C.冒泡排序void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,j,noswap; RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(i=0;in-1;i+) noswap=1; for(j=0;jn-i-1;j+) (*compare)+; if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 算法思想：将被排序的记录数组R1.n垂直排列，每个记录Ji看作是重量为Ji.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组J：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。DShell排序void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange) int i,j,increment; RecordNode temp; SortObject *pvector; if(pvector=(SortObject*)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(increment=d;increment0;increment/=2) for(i=increment;in;i+) temp=pvector-recordi; (*exchange)+; j=i-increment; while(j=0&temp.keyrecordj.key) (*compare)+; pvector-recordj+increment=pvector-recordj; (*exchange)+;j-=increment; pvector-recordj+increment=temp; (*exchange)+; free(pvector);当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。E堆排序void HeapSort(SortObject *p,unsigned long *compare,unsigned long *exchange)/*5.堆排序*/ int i,n; RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;n=pvector-n;for(i=n/2-1;i=0;i-)SiftHeap(pvector,n,i,compare,exchange);/*首先构造第一个堆*/for(i=n-1;i0;i-) temp=pvector-record0; pvector-record0=pvector-recordi; pvector-recordi=temp; (*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange);/*重建新堆*/free(pvector);当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。F快速排序void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/ int i,j; RecordNode temp; if(left=right) return; i=left; j=right; temp=pvector-recordi; (*exchange)+; while(i!=j) while(pvector-recordj.key=temp.key)&(ji) (*compare)+; j-;if(irecordi+=pvector-recordj;(*exchange)+; while(pvector-recordi.keyi)(*compare)+;i+; if(irecordj-=pvector-recordi;(*exchange)+; pvector-recordi=temp; (*exchange)+; QuickSort(pvector,left,i-1,compare,exchange); QuickSort(pvector,i+1,right,compare,exchange);对于n个成员，快速排序法的比较次数大约为n*logn 次，交换次数大约为(n*logn)/6次。如果n为100，冒泡法需要进行4950 次比较，而快速排序法仅需要200 次，快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2)，而平均时间复杂度为O(n*logn)。G排序主调用函数上面说明各种排序函数都是在这里调用的。排序对象长度分别去20,100,500这三种，每种都有6中算法，每种算法都有两个返还值：比较和移动次数，故这里定义了一个二维表number312，类型为unsigned long型（因为比较次数和移动的次数最多可以超过百万）。要产生一些不同的随机数，必须开始调用函数randomize()初始随机化种子，不然每次得到的随机数都是一样的。循环执行三次，每次都得到一种长度的比较移动次数。这里把快速排序放到最后调用，这样，虽然调用此函数后排序对象是有序的，但不影响程序比较算法性能这一目的。最后，再用一个for循环把运行得到的比较结果输出。用一个判断语句，实现前面几个在显示后在出现的一个提示信息：“Press any key to continue”，最后一个没有提示，按任意键退出程序。void SortMethod(void) int i,j; unsigned long num312=0; SortObject *pvector=(SortObject *)malloc(sizeof(SortObject); randomize(); for(j=0;j3;j+) for(i=0;irecordi.key=random(500); pvector-n=MAXSORTNUMj; InsertSort(pvector,&numj0,&numj1); SelectSort(pvector,&numj2,&numj3); BubbleSort(pvector,&numj4,&numj5); ShellSort(pvector,4,&numj6,&numj7); HeapSort(pvector,&numj8,&numj9); QuickSort(pvector,0,MAXSORTNUMj-1,&numj10,&numj11); printf(nSort Method Compare As Follows:); for(j=0;j%-7ld Exchanged-%-7ldn,numj0,numj1); printf(2.SelectSort Method: Compared-%-7ld Exchanged-%-7ldn,numj2,numj3); printf(3.BubbleSort Method: Compared-%-7ld Exchanged-%-7ldn,numj4,numj5); printf(4.ShellSort Method: Compared-%-7ld Exchanged-%-7ldn,numj6,numj7); printf(5.HeapSort Method: Compared-%-7ld Exchanged-%-7ldn,numj8,numj9); printf(6.QuickSort Method: Compared-%-7ld Exchanged-%-7ldn,numj10,numj11); if(j!=2) printf(Press any key to continue.n); getchar(); void main() SortMethod(); 第四章 运行与测试此程序功能是比较各种排序算法的时间复杂度，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。程序运行时出现如图4.1所示界面。图4.1 20个数据排序比较结果这是长度为20的6总排序算法的比较次数和移动次数统计，中间用逗号隔开。最下一行提示用户还有待输出数据“Press any key to continue. ”，按任意键后继续显示。其中如若用冒泡排序，则要比较次数为175，交换次数为273次，这和冒泡排序比较次数3（n-i）=1/2（n*n-n）=190，交换次数为（n-i）=3/2（n*n-n）=270平均情形相近。而这种排序的改进方法快速排序的比较次数为31，交换次数51,显然快速排序性能优于冒泡排序。类似分析长度可选为100和长度可选为500时各个算法的执行情况，分别作图4.2和图4.3所示图4.2 100个数据排序比较结果图4.3 500个数据排序比较结果可以看到，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序虽然交换次数很少，但比较次数较多。第五章 总结排序算法是是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工