《论文——排序算法时间效率的比较》由会员分享，可在线阅读，更多相关《论文——排序算法时间效率的比较（26页珍藏版）》请在金锄头文库上搜索。
1、毕业论文各种排序算法性能比较系专业姓名班级学号指导教师职称设计时间目录摘要第二章 排序基本算法 3第三章 系统设计11第四章 运行与测试 24第五章 总结 26摘要排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、 操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各 种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。本毕 业论文对直接插入排序、直接选择排序、起泡排序、Shel 1排序、快速排序以及堆排 序算法进行比较。我们设置待排序表的元素为整数，用不同的测试数据做测试比较，长度取固定 的三种，对象由随机数生成，无需人工干预来选择或者输
2、入数据。比较的指标为关 键字的比较次数和关键字的移动次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这六 种算法中，快速排序比较和移动的次数是最少的。也是最快的一种排序方法。堆排 序和快速排序差不多，属于同一个数量级。直接选择排序虽然交换次数很少，但比 较次数较多。关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序;1.3 本文主要内容排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法 每一种方法都有各自的优缺点，适合在不同的环境下使用。如果排序中依据的不同 原则对内部排序方法进行分类，则大致可分为直接插入排序、直接选择排序、
3、起泡 排序、Shel 1排序、快速排序、堆排序六类。本文编写一个程序对直接插入排序、直接选择排序、起泡排序、Shel 1排序、快 速排序及堆排序这几种内部排序算法进行比较，用不同的测试数据做测试比较。比 较的指标为关键字的比较次数和关键字的移动次数。最后用图表数据汇总，以便对 这些内部排序算法进行性能分析。第二章 排序基本算法2.1 直接插入排序2.1.1 基本原理假设待排序的n个记录RO, Rl, Rn顺序存放在数组中，直接插入法在插 入记录Ri(i=1, 2,，n-1)时，记录被划分为两个区间R0,Ri-1和Ri+1,Rn-1,其中， 前一个子区间已经排好序,后一个子区间是当前未排序的部分
4、,将关键码 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 2
5、0 25 (将 8 放入适当的位置)2.1.3 时间复杂度分析直接插入排序算法必须进行 n-1 趟。最好情况下，即初始序列有序，执行 n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1),移动元素次数是 2(n-1 )。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较 i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。2.2 直接选择排序2.2.1 基本原理待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素 交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环 到只剩下最后一个数据元素为止，依次类推直到所有记录
6、。第一趟第 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
7、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 基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经 过
8、一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列(IOIn-l)中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1 次；第一趟排序结束，最大元素被交换到In-1中，下一趟只需在子序列(I0In-2)中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。 将被排序的记录数组J1 n垂直排列，每个记录Ji看作是重量为Ji.key的气 泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本 原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻 者在上，重者在下为止，最后可完成。2.3.2 排序过程将被排序的记录数组R1 n垂直排列
9、，每个记录Ri看作是重量为Ri.key 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反 本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是 轻者在上，重者在下为止。( 1 )初始R1.n为无序区。( 2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者 在上，则交换二者的位置。即依次比较(Rn, Rn-1), (Rn-1, Rn-2),， (R2, R1)；对于每对气泡(Rj+1，Rj)，若 Rj+l.keyRj.key，则交换 Rj+1和Rj的内容。第一趟扫描完毕时， 最轻的气泡就飘浮到该区间的顶部，即关键字最小的
10、 记录被放在最高位置Rl上。( 3)第二趟扫描扫描R2,n。扫描完毕时，次轻的气泡飘浮到R2的位置上,最后, 经过n-1趟扫描可得到有序区Rln。第i趟扫描时,Rli-1和Rin分别为当前的有序区和无序区。扫描仍是 从底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置Ri上， 结果是R1i变为新的有序区。初始数据763246805546*第一轮：第一趟排序后327646805546*第二趟排序后324676805546*第三趟排序后324676805546*第四趟排序后324676558046*第五趟排序后3246765546*80第二轮排序结果32465546*7680第三轮排序
11、结果324646557680第四轮排序结果324646*557680第五轮排序结果324646*:5576802.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的
12、名字命 名的.Shell排序法是对相邻指定距离(称为间隔)的元素进行比较，已知到使用当前 间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理，当间 隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整 数 d1n, 把全部记录分成 d1 个组，所有距离为 d1 倍数的记录放在一组中，先在各组 内排序；然后去 d2d1 重复上诉分组和排序工作；直至所取的增量dt=l（dtdtTd2dl），即所有记录放在同一组中进行直接插入，直到dt=l,即 所有记录放在一组中为止。2.4.2 排序过程先取一个正整数d1n，把所有序号相隔di的数组元素放一组，组
13、内进行 直接插入排序；然后取d2di，重复上述分组和排序操作；直至 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=l）: 04 13 27 38 48 49 55 65 76 972.4.3 时间复杂度分析希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候， 步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很 小，插入排序
14、对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 o（n2） 好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素 的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移 动，最后其稳定性就会被打乱，所以 shell 排序是不稳定的。所以希尔排序是不稳定 的，其时间复杂度为 o（n2）。2.5堆排序2.5.1 基本原理堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一 个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程 直到堆中只剩一个元素,n个关键字序列kl , k2，kn称为堆，当且仅当该 序列满足如下性质
15、（简称为堆性质）：（l） ki= k2i且ki=k2i 且ki=k2i+l。若将此序列所存储的向量R 1n看作是一棵完全二叉树的存储结 构，则堆实质上是满足如下性质的完全二叉树:树中非叶结点的关键字均不大于（或 不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是 堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是 堆里所有结点关键字中最大者，称为大根堆。注意： 堆中任一子树亦是堆。 以上讨论的堆实际上是二叉堆，类似地 可定义 k 叉堆。2.5.2 排序过程堆排序是一树形选择排序。堆排序的特点是：在排序过程中，将 R1n 看 成是一棵完全二叉树的顺序存储结
