不同排序算法的实现和性能比较.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.65M 资料格式：doc 举报版权申诉

yingmeng9913-5331137-4744302542960937709.doc.pdf-第1页.png

第1页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第2页.png

第2页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第3页.png

第3页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第4页.png

第4页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第5页.png

第5页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第6页.png

第6页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第7页.png

第7页 / 共18页

yingmeng9913-5331137-4744302542960937709.doc.pdf-第8页.png

第8页 / 共18页

一、引言

二、排序算法

三、算法实现及性能比较

四、算法性能分析

五、结论

附录

不同排序算法的实现和性能比较（本人用 C++类编写的代码，不喜勿入） 1

目录一、引言 ........................................................... 3 二、排序算法 ....................................................... 3 三、算法实现及性能比较 ............................................. 4 四、算法性能分析 ................................................... 8 五、结论 .......................................................... 10 附录 .............................................................. 11 2

一、引言排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。二、排序算法排序是计算机内部经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列，其可分为内部排序和外部排序（这里我们所说的排序只指前者）。下面我们将对这五中算法进行简单介绍和分析，然后通过实验数据给出五种中算法的性能比较。 (1) 插入排序（insertion sort）：插入排序的思想是将一组无序的元素（这里我们用正整数来代替）分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组 n[1…r]为初始的一个无序数组（为了直观起见，我们这里设定数组从 1 开始，而不是 0），则 n[1]默认为只有一个元素的有序数组，n[2]插入只有 n[1]构成的有序数组中，则此时有序数组的元素数量变为 2。以此类推，到第 i 个元素时，前 i-1 个元素已经是有序的，此时只需将第 i 个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。 (2) 冒泡排序（bubble sort）：冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。 (3) 堆排序（heap sort）：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结构——堆来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的所有节点（这里描述的是小根堆，大根堆的话情况恰好相反）， n[i]<=n[2*i]&&n[i]<=n[2*i+1]。因此堆排序算法首先要将给出的无序数组构造成一个堆，然后输出根节点（最小元素），将剩余元素重新恢复成堆，再次输出根节点。依次类推，直至最后一个节点输出，此时堆排序完成。 (4) 合并排序（merge sort）：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组 n[1…r] 分成两个数组 n[1…r/2]与 n[r/2+1…r]，分别对这两个小数组进行合并排序，然后 3

再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。 (5) 快速排序（quick sort）：如上所述，快速排序也是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是分割或 partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序。三、算法实现及性能比较这里通过 c++语言来实现各种排序算法（源码见附录），程序运行环境为 windows 7，所用编译器为 vs2010。如图 1 所示图 1 控制台程序实验结果：实验分别实现插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同规模（100，1000，2000，5000，10000，100000 个数据）的随机数作为测试数据集，实验结果截图如下： 4

排序规模为 100 排序规模为：1000 5

排序规模为：2000 排序规模为：5000 6

排序规模为：10000 排序规模为：100000 7

四、算法性能分析在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相同的输入规模中原始无序数据都是一样的。例如五种排序算法要对长度为 100 的无序数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主要参数（排序时间作为辅助参数）。表 1 为在输入规模分别为 100，1000，2000， 5000，10000，100000 时各个算法的元素交换次数。表 2 为在输入规模分别为 100， 1000，2000，5000，10000，100000 时各个算法的排序时间。排序规模（n） 100 1000 2000 5000 10000 100000 算法插入排序冒泡排序堆排序合并排序快速排序 2782 2684 1000 555 599 6266052 246255 5956790 242011 106026 16480 55301 8719 10377 71431 表 1 排序算法比较次数性能比较 983211 963158 37063 19432 23702 24870816 22452014 231903 120409 152879 2509250617 1127169842 2985016 1536596 1946925 排序规模（n） 100 1000 2000 5000 10000 100000 算法插入排序冒泡排序堆排序合并排序快速排序 0.0452 0.1007 0.0737 0.3709 0.0335 3.0583 9.46976 0.579467 2.19143 0.202953 12.1263 21.3535 1.28444 4.11925 0.428768 58.2854 133.777 3.59577 11.6794 1.3171 177.54 526.971 8.03182 20.8016 2.69531 16694 42698.7 102.961 192.61 29.9569 表 2 排序算法排序时间比较（单位 ms）为了直观起见，根据实验数据画出各种排序算法在不同输入规模下交换次数的变化趋势图如图 2 所示： 8

分享到：

赞收藏

资料库

不同排序算法的实现和性能比较.doc

相关推荐

课程资源

热门标签

最新资料