发布时间 : 星期二 文章数据结构各种排序算法的时间性能更新完毕开始阅读06944ca3a9114431b90d6c85ec3a87c241288a03
（六）算法性能分析
在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相同的输入规模中原始无序数据都是一样的。例如五种排序算法要对长度为100的无序数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主要参数（排序时间作为辅助参数）。表1为在输入规模分别为100，1000，2000，5000，10000，100000时各个算法的元素交换次数。表2为在输入规模分别为100，1000，2000，5000，10000，100000时各个算法的排序时间。
100 排序规模（n） 算法 插入排序 冒泡排序 堆排序 合并排序 快速排序 2782 2684 1000 555 599 1000 246255 242011 16480 8719 10377 2000 983211 963158 37063 19432 23702 5000 6266052 5956790 106026 55301 71431 10000 24870816 22452014 231903 120409 152879 100000 2509250617 1127169842 2985016 1536596 1946925 表1 排序算法比较次数性能比较
100 排序规模（n） 算法 插入排序 冒泡排序 堆排序 合并排序 快速排序 0.0452 0.1007 0.0737 0.3709 0.0335 1000 3.0583 9.46976 0.579467 2.19143 0.202953 2000 12.1263 21.3535 1.28444 4.11925 0.428768 5000 58.2854 133.777 3.59577 11.6794 1.3171 10000 177.54 526.971 8.03182 20.8016 2.69531 100000 16694 42698.7 102.961 192.61 29.9569 表2 排序算法排序时间比较（单位ms）
为了直观起见，根据实验数据画出各种排序算法在不同输入规模下交换次数的变化趋势图如图2所示：
图2排序算法交换次数趋势图
由上图我们基本上看出插入排序和冒泡排序的比较次数随输入规模的呈非线性增长，而后三种排序方法——堆排序，合并排序，快速排序的比较次数随输入规模的增长基本呈线性变化趋势。
根据实验数据画出各种排序算法在不同输入规模下交换次数的变化趋势图如图3所示：
图3排序算法排序时间趋势图（单位：ms）
实验结果与我们对这五种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。图4还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序时间方面。
（七）结论
最后得出结论： 时间性能上，
快速排序 > 堆排序 > 合并排序 > 插入排序 > 冒泡排序 交换次数上，
合并排序 > 快速排序 > 堆排序 > 冒泡排序 > 插入排序
(八)心得
作为拿来复习的一个报告还是蛮有成就感的，但是输入1000000个数据的时候等得太久，实在等不出结果，而且放入值太大不方便作图，于是就不参与数据分析，但是估计结果应该相同。以前不懂排序只会用冒泡，因为冒泡排序是接触编程的第一个排序，印象很深刻，而且几乎不会用错，当数据比较大时它的弊端就真的出现了。本以为这个实验还是比较好做的，排序几乎都会，连助教都说一句你这个选题太没难度了。但是平心而论，真正实现起来还真是问题多多，首先是怎么样调用时间的问题，这也是第一个先想的问题，本来打算就只比较交换次数和比较次数的，但是这些其实没有比时间更直观的反应排序的效率。寻找半天无果本来都打算放弃了，结果竟然有一个回复贴说QueryPerformanceCounter函数，于是就发现这个问题可以解决了。结果是想象的有点偏差，没想到堆排序的速度也能这么快，合并排序的次数会那么少。本以为快速排序就是万能的了，看来想多了。或许以后在研究算法方面的确需要好好分析效率，数据结构的确是一门很有用的学科，以后不能丢弃。