毕业论文
    各种排序算法性能比较 
      系                                 
      专业                            姓名       
      班级                  学号         
指导教师          　 职称         
设计时间                           
目录
摘要    2
第二章 排序基本算法    5
第三章 系统设计    16
第四章 运行与测试    29
第五章 总结    31
摘要
排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本毕业论文对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序以及堆排序算法进行比较。
我们设置待排序表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的比较次数和关键字的移动次数。
经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序虽然交换次数很少，但比较次数较多。
关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序；
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 97
2.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）初始
    ]为无序区。
（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  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排
序也就完成了其处理过程.先取一个整数d1<n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2<d1重复上诉分组和排序工作；直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入，直到dt=1，即所有记录放在一组中为止。
2.4.2排序过程
先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。