算法--排序算法效率比较

实验名称：排序算法效率比较

实验地点：

所使用的开发工具及环境：   PC机，DEV++

一、实验目的：

比较至少 4 种排序（从小到大排）算法的执行效率。已学过的算法：冒泡排序、选择排序、插入排序、shell 排序，归并排序、快速排序等。  

三、实验内容。

1、随机产生 50000+个数据，并保存至文件 test 中。

核心代码：

2、至少编写 4 种排序算法。

（1）冒泡排序：

（2）插入排序：

（3）选择排序：

（4）快速排序：

（5）归并排序：

3、调用步骤 2 中编写的程序，并从 test 中读取数据并排序，输出从读取到排好序，总共需要的时间。

4、结合时间复杂度，验证并分析几种排序算法的优劣。

（1）冒泡排序(Bubble Sort)的时间复杂度为O(n^2)。

（2）选择排序(Selection Sort)的时间复杂度也为O(n^2)。

（3）插入排序(Insertion Sort)的时间复杂度也为O(n^2)

（4）快速排序的平均时间复杂度为O(nlogn)。

（5）归并排序的平均时间复杂度为O(nlogn)。

在上述实验中测试的数据时间从大到小的排序是：选择>插入>冒泡>快速>归并。所以，综上所述，快速排序和归并排序不论是从时间复杂度来讲还是实际操作中所用的时间来说，都要比其他（实验中的的选择排序，插入排序，冒泡排序）算法来讲，都要好得多。

5、如果随机生成的数据是基本有序，或者是有序，或者是反序时，运行结果会怎么样？怎样解决这种问题，试提出你的解决方法。

冒泡排序、选择排序和插入排序的性能会受到较大影响，而快速排序在不同数据情况下的性能相对更为稳定。

归并排序在任何情况下都能保持稳定的O(n log n)时间复杂度，因此在基本有序、有序或反序的情况下，性能都相对稳定。

解决这种问题的方法之一是通过检测数据的有序程度，在数据已经有序或接近有序的情况下，采用更适合的排序算法以提升性能。

四、程序运行结果分析。

就之前的实验步骤中的操作来说，选择>插入>冒泡>快速>归并是此次实验的结论，快速排序和归并排序不论是从时间复杂度来讲还是实际操作中所用的时间来说，都要比其他实验中的选择排序，插入排序，冒泡排序算法来讲，都要好得多，但是归并排序不会受数据顺序的影响，在所有情况下都很稳定。并且冒泡排序、选择排序和插入排序的性能会受到较大影响，而快速排序在不同数据情况下的性能相对更为稳定。

五、实验总结

此次实验比较至少 5 种排序算法的执行效率，分别将冒泡排序、选择排序、插入排序、快速排、归并排序，五种算法进行比较。增强了我们的动手能力和编程能力，以及将算法进行实际应用的能力。