《算法分析与设计》排序算法性能测试实验报告_排序算法的实现实验报告

一、实验要求

对几个经典的排序算法进行分析，理解算法在不同输入时的表现，深入剖析算法优缺点及其根源。具体要求如下：
1.以给出的插入排序算法为例，实现几种排序算法，至少要实现冒泡排序、快速排序、归并排序、shell排序算法；
2.在排序算法中打桩，记录关键操作次数（例如比较次数、移动次数）；
3.以待排序数组的大小n为输入规模，固定n，随机产生大量测试样本，统计不同排序算法的平均运行时间和关键操作次数，并进行记录；
4.改变数组规模，对不同规模问题各算法的结果对比分析，通过统计画图，与理论值进行对照分析，并撰写实验报告。
5.附加：对快速排序的几种不同的实现进行性能比较；对快速排序进行优化，对优化前后的性能进行分析。

二、实验报告

1.实验设计

1.1 函数介绍

本实验的主要文件为Sort.cpp，该文件中主要实现了6个函数，其中包含了Shell_Sort,Bubble_Sort,Quick_Sort_Recursive,Quick_Sort_Recursive_Opt_1,Quick_Sort_Recursive_Opt_2,Merge_Sort（本实验最大n为1e6）。

1.2 代码功能描述

本实验的Sort.cpp文件完成了冒泡排序、快速排序、归并排序、shell排序，并通过cmp_count和move_count变量分别记录了排序过程中的比较次数和移动次数这两个关键步骤。运行本实验代码的命令行如下：
./Sort < selector > < scale >
其中selector为选择子，通过选择子来测试不同的排序算法，scale为第3个问题中固定n的大小。
本实验在选定测试算法后，会解决第3和第4个问题。其中在解决第3个问题时，会生成Rep（在文件开始时定义为10）组数据进行排序，并返回平均比较次数的移动次数。在解决问题4时 ，n从10000增长到100000，步长为10000,测试每一个n的时间、比较次数和移动次数。

2.实验原理

2.1 冒泡排序

冒泡排序的基本原理是两两比较待排序数据的大小 ，当两个数据的次序不满足顺序条件时即进行交换，反之，则保持不变，这样每次最小(或最大)的结点就像气泡一样浮到序列的最前位置。设有 n 个数的序列，即数组 a(1)～a(n)，要求按递增(或递减 )的顺序排列，即冒泡排序。

2.2 快速排序

快速排序的基本原理是在待排序的数列中，我们首先要找一个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

2.3 归并排序

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

2.4 Shell排序

希尔排序是按照不同步长对元素进行插入排序。当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。

3.运行指导

本实验编写了7个脚本文件，分别为test_x.sh(x:0-5)和test_all.sh，x表示了选择子，test_all.sh测试所有的排序算法，并且将结果写入了csv文件中。关于选择子的说明说下表所示，

使用说明：
1.将Sort.cpp与*.sh文件拷贝至Linux系统中
2.使用命令*chmod 777 .sh
3.根据需要运行脚本文件,例如 ./test_all.sh（脚本文件中已经包含编译命令）
4.结果保存在csv文件中

4. 实验结果

4.1 冒泡排序

图1为冒泡排序的移动次数、比较次数和运行时间随规模n变化而变化的曲线图，其中图中Theoretical value 的值为 scale(i) * scale(i)。通过图1可以看出冒泡排序中的一些关键步骤，如实验中的移动次数和比较次数的大小为O（n ** 2）。运行时间的拟合方程为
$$T(n)=3\ast 10^{-9}\ast n^2$$
故时间复杂度的大小为O(n**2)。

								图1 冒泡排序
1

4.2 快速排序

4.2.1 递归快速排序

图2为递归实现的快速排序的移动次数，比较次数和运行时间岁规模n变化而变化的曲线图，其中Theoretical value 的值为 scale(i) * log(2,scale(i))。通过图2可以看出快速排序中关键步骤，如实验中的移动次数和比较次数次为O(nlogn)，与冒泡排序相比快速排序的比较次数与移动次数的差值较大，故可以与快速排序中的大范围移动的结论相印证。运行时间的拟合函数为
$$T(n)=1.15\ast 10^{-8}\ast nlo{g}_{2}n$$

						图2 使用递归的快速排序
1

4.2.2 递归排序算法优化1

图3为使用中间值作为基准值的递归实现的快速排序的移动次数，比较次数和运行时间随着规模n变化而变化的曲线图。从图像中可以看出，优化后的算法比较次数减少，运行时间减少。运行时间的拟合函数为
$$T(n)=9\ast 10^{-9}\ast nlo{g}_{2}n$$
故时间复杂度为O(nlogn)。

							图3 使用优化递归的快速排序
1

4.2.3 递归快速排序优化2

图4为使用三数取中法选择基准值的方法优化递归实现的快速排序的移动次数、比较次数和时间随规模n变化而变化的曲线图。从图中可以看，优化后比较次数减少，运行时间减少。这样选择基准值使出现最坏情况的概率减小，故快速排序算法得到优化。运行时间的拟合函数为
$$T(n)=9\ast 10^{-9}\ast nlo{g}_{2}n$$
故时间复杂度为O(nlogn)。

							图4 使用迭代的快速排序
1

4.3 归并排序

图5 为归并排序的移动次数、比较次数和运行时间随规模n变化而变化的曲线图归并排序的移动次数多于快速排序，但是比较次数相对于快速排序较小。移动次数与和较次数与Theoretical value = scale(i)*log(2,scale(i))相近，为O(nlogn) 。运行时间的拟合方程为
$$T(n)=10^{-8}\ast nlo{g}_{2}n$$
故时间复杂度为O(nlogn)。

												图5 归并排序
1

4.4 Shell 排序

图5为Shell排序的移动次数、比较次数和运行时间随规模n变化而变化的曲线图。其中移动次数和比较次数与Theoretical value = scale(i) ** 1.3相近，为O(n ** 1.3)。运行时间的拟合方程为
$$T(n)=7.5\ast 10^{-9}\ast n^{1.3}$$
故时间复杂度为O(n**1.3)。

							图6 Shell排序
1

三、时间复杂度分析

1.冒泡排序

在完全有序的情况下，最好的时间复杂度是O(n)，只需要1次冒泡。而在极端情况完全逆序，时间复杂度为O(n** 2)。在分析平均复杂度时使用到两个概念：有序度和逆序度。
有序度的定义为：数组中具有有序关系的元素对的个数，即如果i<j,则a[i]<a[j]。
1.逆序度的定义为：数组中具有逆序关系的元素对的个数，即如果i<j,则a[i]>a[j]
2.有序度与逆序度的关系：有序度 + 逆序度 = 满有序度 。排序就是增加有序度的过程，一直到有序度等于满有序度，而逆序度为0。
排序过程每交换一次，有序度加1，逆序度减1，比如刚开始原数组的有序度为x，那么逆序度=n(n-1)/2-x.也就是最终有序需要交换的次数。如果初始有序度x=0，那就是最坏的情况，逆序度为n(n-1)/2；如果有序度x为n(n-1)/2,那这就是最好的情况，逆序度为0，根本不需要交换。因此，可以取一个初始有序度不好也不坏的情况x=n(n-1)/4,最终交换的次数，即逆序度就等于n(n-1)/4,换算成时间复杂度就是O(n ** 2).

2.快速排序

设n为待排序数组中的元素个数，T(n)为算法需要的时间复杂度，则

其中D(n)=n - 1，是一趟快速排序需要的比较次数，一趟快速排序后将数组分 成两部分I1和I2。
最好的情况下，每一次划分都正好将数组分成长度相等的两半
所以，

最坏的情况下，每一次划分都将数组分成了0和n-1两部分

所以，

在任意一种划分情况都出现的概率都相等的情况下，

所以，

下面通过递归求解B(n)的表达式，然后将B(n)带回求解T(n)

3.归并排序

设n为待排序数组中的元素个数，T(n)为算法需要的时间复杂度，则

其中C(n)是将两个含有n/2个数据元素的序列合并为一个含有n个数据元素的序列所需要的比较操作次数。
最好的情况下，刚好一个序列的最后一个值是另一个序列的最小值时，C(n)=n/2，所以

最坏的情况下，当两个序列各个元素的大小交叉排列时，C(n)=n-1，所以

综上所述，归并排序的平均时间复杂度为O(nlogn)。