1 不同排序算法的实现和性能比较 学 院 信息学院 专 业 计算机系统结构 姓 名 张 凯 歌 学 号 1201001179 指导教师 岳昆（副教授） 2
一、引言 ................................................................................................................................... 3 二、排序算法 ........................................................................................................................... 3 三、算法实现及性能比较 ....................................................................................................... 4 附录 .................................................................................................................................................. 9 参考文献......................................................................................................................................... 16 3 一、引言 排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。 在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。
二、排序算法 排序是计算机内部经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列，其可分为内部排序和外部排序（这里我们所说的排序只指前者）。下面我们将对这五中算法进行简单介绍和分析，然后通过实验数据给出五种中算法的性能比较。 (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
(4) 合并排序（merge sort）：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n[1…r]分成两个数组n[1…r/2]与n[r/2+1…r]，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。 (5) 快速排序（quick sort）：如上所述，快速排序也是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是分割或partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序。
三、算法实现及性能比较 这里我们通过c++语言来实现各种排序算法（源码见附录），程序运行环境为windows xp，所用编译器为vc++ 6.0。如图1所示
图1 windows xp操作系统 在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同 5
的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相同的输入规模中原始无序数据都是一样的。例如五种排序算法要对长度为100的无序数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主要参数（排序时间作为辅助参数）。表1为在输入规模分别为100,1000,2000,5000,10000,100000时各个算法的元素比较次数。 输入规模（n） 排序算法 100 10000 2000 5000 10000 100000
插入排序 2563 263217 1024775 6424426 24802709 2501929440 冒泡排序 4719 499423 1991201 12468181 49935611 704207961 堆排序 881 17530 37024 107023 232028 2975620 合并排序 535 7697 2942 55284 120347 1536091 快速排序 597 10085 22867 80143 157751 2104103 表1 排序算法比较次数性能比较 为了直观起见，我们根据实验数据画出各种排序算法在不同输入规模下比较次数的变化趋势图如图2所示：
五种排序算法性能比较图
020004000600080001000012000102030405060708090100110120130140150输入规模比较次数插入排序冒泡排序堆排序合并排序快速排序
图2排序算法性能趋势图 由上图我们基本上看出插入排序和冒泡排序的比较次数随输入规模的呈非线性增长，而后三种排序方法——堆排序，合并排序，快速排序的比较次数随输入规模的增长基本呈线性变化趋势。因此我们在这里暂且将前两种排序归类为低效排序算法，而将后三种归类为高效排序算法。图3和图4更加清楚地显示了这两类算法的变化趋势。 6
图4插入与冒泡排序性能比较图 堆，合并与快速排序性能分析
050000100000150000200000250000300000350000400000100030005000700090001100013000规模比较次数堆排序合并排序快速排序
图5高效排序算法性能分析图 实验结果与我们对这五种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。图4还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好。 关于图5我们仍有一点要说明，就是从比较次数上看合并排序似乎是最高效
插入与冒泡排序性能比较图020000000400000006000000080000000100000000120000000
1000200030004000500060007000800090001000011000120001300014000
输入规模
比较次数插入排序
冒泡排序 7 的算法，但我们知道快速排序才是排序算法中最快的算法，这里理论似乎和实验结果出现了矛盾。下面我们以算法执行的时间来进行辅助说明，如表2所示：
次数 计数排序 基数排序 堆排序 快速排序 希尔排序 直接插入排序 冒泡排序 1 0.0000 0.0310 0.0470 0.0470 0.0310 14.7970 58.0930 2 0.0000 0.0470 0.0310 0.0470 0.0470 16.2500 53.3280 3 0.0000 0.0310 0.0310 0.0310 0.0310 14.4850 62.4380 4 0.0000 0.0320 0.0320 0.0470 0.0310 17.1090 61.8440 5 0.0000 0.0310 0.0470 0.0470 0.0310 16.9380 62.3280 6 0.0000 0.0310 0.0310 0.0470 0.0310 16.9380 57.7030 7 0.0000 0.0310 0.0470 0.0310 0.0310 16.8750 61.9380 8 0.0150 0.0470 0.0310 0.0470 0.0320 17.3910 62.8600 9 0.0000 0.0320 0.0470 0.0460 0.0310 16.9530 62.2660 10 0.0000 0.0470 0.0310 0.0470 0.0310 17.0160 60.1410 11 0.0000 0.0930 0.0780 0.0320 0.0310 14.6090 54.6570 12 0.0000 0.0310 0.0320 0.0310 0.0310 15.0940 62.3430 13 0.0000 0.0310 0.0310 0.0470 0.0310 17.2340 61.9530 14 0.0000 0.0320 0.0470 0.0470 0.0310 16.9060 61.0620 15 0.0000 0.0320 0.0320 0.0460 0.0320 16.7810 62.5310 16 0.0000 0.0470 0.0470 0.0620 0.0310 17.2350 57.1720 17 0.0150 0.0160 0.0320 0.0470 0.0310 14.1400 52.0320 18 0.0150 0.0160 0.0310 0.0310 0.0310 14.1100 52.3590 19 0.0000 0.0310 0.0320 0.0460 0.0320 14.1090 51.8750 20 0.0000 0.0310 0.0320 0.0460 0.0320 14.0780 52.4840 21 0.0150 0.0780 0.0470 0.0470 0.0310 16.3750 59.5150 22 0.0000 0.0310 0.0310 0.0470 0.0320 16.8900 60.3440 23 0.0000 0.0310 0.0310 0.0310 0.0310 16.3440 60.0930 24 0.0000 0.0310 0.0310 0.0470 0.0310 16.3440 60.5780 25 0.0000 0.0320 0.0470 0.0470 0.0470 16.3590 59.7810 26 0.0160 0.0470 0.0310 0.0470 0.0310 16.1250 61.0620 27 0.0000 0.0310 0.0470 0.0470 0.0310 16.7810 59.6100 28 0.0150 0.0320 0.0320 0.0470 0.0310 16.9220 56.8130 29 0.0000 0.0310 0.0310 0.0310 0.0310 15.0790 57.8120 30 0.0000 0.0310 0.0320 0.0460 0.0320 14.7810 58.8280 31 0.0000 0.0310 0.0310 0.0470 0.0310 15.8590 59.1400 32 0.0000 0.0470 0.0320 0.0310 0.0310 16.0940 59.1560 33 0.0000 0.0470 0.0310 0.0310 0.0310 15.9850 59.1400 34 0.0000 0.0310 0.0310 0.0470 0.0320 16.0150 59.2500 35 0.0000 0.0310 0.0470 0.0470 0.0310 16.7660 57.9840 36 0.0000 0.0310 0.0320 0.0470 0.0310 15.3750 59.0470 37 0.0000 0.0320 0.0460 0.0470 0.0320 16.0310 58.9060 38 0.0000 0.0310 0.0310 0.0470 0.0310 15.9530 57.2650 39 0.0160 0.0310 0.0470 0.0470 0.0310 15.9530 57.5160 40 0.0150 0.0310 0.0320 0.0470 0.0310 14.7030 56.6710