《算法设计与分析》课程实验报告 （ 实验一）
| 实验名称：排序算法效率比较 | 实验地点： |
| 所使用的开发工具及环境： PC机，DEV++ | |
| 一、实验目的： 比较至少 4 种排序（从小到大排）算法的执行效率。已学过的算法：冒泡排序、选择排序、插入排序、shell 排序，归并排序、快速排序等。 | |
| 二、基本思想、原理和算法描述： 本次实验中使用到的冒泡排序、选择排序、插入排序、快速排序四种排序算法，它们的基本思想、原理和算法描述如下: （1）冒泡排序： 重复遍历数组，每次遍历将当前最大的元素冒泡到最后。对于未排序部分，从数组首元素开始，依次比较相邻的两个元素。 （2）选择排序： 对于未排序部分，从数组首元素开始，逐个选择最小（或最大）的元素。将选出的最小（或最大）元素与未排序部分的首元素交换位置，将其放到已排序部分。重复上述步骤，直到全部排序完成。 （3）插入排序： 将数组分为已排序和未排序两部分，初始时已排序部分只包含一个元素（即数组的第一个元素）。从未排序部分选择一个元素，将它插入到已排序部分的正确位置，使已排序部分仍然有序。重复上述步骤，直到未排序部分为空。 （4）快速排序： 选择一个基准元素，一般选择数组的最后一个元素。将比基准小的元素移到左侧，比基准大的元素移到右侧。可以使用双指针或单指针的方式进行分区操作。对基准元素左右的两个分区分别进行递归快速排序。重复上述步骤，直到每个分区只包含一个元素或为空。 （5）归并排序： 分割：将待排序的数组分割为两个子数组，找到数组的中间位置 mid = (left + right)/2，其中 left 表示数组的起始位置，right 表示数组的终止位置。 递归排序：对左右两个子数组分别递归调用归并排序函数 mergeSort，将其分割为更小的子数组，并进行排序。 合并：将排好序的左右两个子数组按照大小顺序合并到原始数组中。为此，需要创建一个临时数组 temp，用来存储合并后的结果。设置三个指针：i 指向左子数组的起始位置，j 指向右子数组的起始位置，k 指向临时数组的起始位置。比较左右两个子数组的元素大小，将较小的元素放入临时数组，并将指针向后移动。重复这个过程，直到其中一个子数组的元素全部放入临时数组。将剩余的子数组中的元素直接拷贝到临时数组中，最后将临时数组的元素复制回原始数组相应的位置。 | |
| 三、实验内容。 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 种排序算法的执行效率，分别将冒泡排序、选择排序、插入排序、快速排、归并排序，五种算法进行比较。增强了我们的动手能力和编程能力，以及将算法进行实际应用的能力。 | |
