一、实验目的与要求

1、实验基本要求

①掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理

②掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

2、实验亮点

①除了基本五种排序算法，额外选择了基数排序，希尔排序和堆排序三种排序算法进行性能分析并对一些算法提出优化方案。

②使用Tableau进行绘图，完成数据可视化

③对实验过程中发现的相关问题进行了探究并解决

④分析了每一种情况下理论时间消耗与实际时间消耗偏差的原因。

⑤实现了对部分算法的优化以及思考题对一万亿数据的排序问题

二、实验内容与方法

 排序问题要求我们按照升序排列给定列表中的数据项，目前为止，已有多种排序算法提出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理，并进行代码实现。通过对大量样本的测试结果，统计不同排序算法的时间效率与输入规模的关系，通过经验分析方法，展示不同排序算法的时间复杂度，并与理论分析的基本运算次数做比较，验证理论分析结论的正确性。

三、实验步骤与过程

（一）独立算法性能分析

1. 冒泡排序

（1）算法实现原理

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤，除了最后一个。

④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 下面以使用冒泡排序3,5,1,2这四个数字为例，以图示介绍冒泡排序，见下图

（2）源代码

BUBBLESORT(A)
  for i = 1 to A.length-1
    for j = A.length downto i + 1
      if A[j] < A[j - 1]
        exchange A[j] with A[j - 1]

（3）算法性能分析：

①时间复杂度分析：

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值

所以，冒泡排序最好的时间复杂度为O ( n )

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较( 1 ≤ i ≤ n − 1 ) ，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为O ( n 2 )

综上，因此冒泡排序总的平均时间复杂度为O ( n 2 )

②数据测试分析：

使用随机数生成器生成了从10² 到10⁶的不同数据量级的随机数，通过使用冒泡排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择10⁵ 时运行时间为理论值并做表如下：

通过获得的数据，使用 10⁵

时的时间消耗为基准理论值，使用Tableau做图像并拟合如图：

  由于冒泡排序算法时间复杂度为O (n² )  ，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合O ( n 2 )  )的时间复杂度。

 从上图可知，实际时间消耗曲线与理论时间消耗基本拟合，冒泡排序算法的时间复杂度满足O (n² )

2. 选择排序

（1）算法实现原理

①首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

②从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。

③重复上述过程直至所有元素均排序完毕。

下面以使用选择排序3,5,1,2这四个数字为例，以图示介绍选择排序，见下图

（2）源代码

SELECTSORT(ele)
  for i=0 to n-2
    min=i
    for j= i+1 to n-1
        if ele[min]>ele[j]  min=j
    swap(ele[i],ele[min])

（3）算法性能分析

①时间复杂度分析：

选择排序的交换操作介于0 00与n − 1次之间。选择排序的比较操作为n ( n − 1 ) / 2  次之间。选择排序的赋值操作介于 0 和 3 ( n − 1  次之间。比较次数为O ( n² )

)。比较次数与关键字的初始状态无关，总的比较次数N = ( n − 1 ) + ( n − 2 ) + . . . + 1 = n ( n − 1 ) / 2 交换次数O ( n )，最好情况是，已经有序，交换0次；最坏情况交换n − 1 次，逆序交换n / 2 次。因此选择排序的时间复杂度为O ( n² )

②数据测试分析：

使用随机数生成器生成了从10² 到10⁶的不同数据量级的随机数，通过使用选择排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择10⁵时运行时间为理论值并做表如下：

通过获得的数据，使用10⁵ 时的时间消耗为基准理论值，使用Tableau做图像并拟合如图：

由于选择排序算法时间复杂度为O (n² )，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合O (n² )的时间复杂度。

从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍，时间消耗扩大100倍的规律。但对于10¹，10²

数量级时存在较大误差，拟合效果较差。通过分析可知，选择排序中进行了很多次相互调换元素（相互赋值）的操作，从而造成了时间浪费。我进行了如下两次对比实验，使用库函数swap和手写调换元素的函数进行对比，可以发现，使用swap函数的小数据拟合效果要明显好于手写。因此，小数据下，较差的拟合效果是因为较多次交换占用了更多时间，当数据较小时，数据交换造成的时间损耗更明显。但当数据变多时，这种影响被冲淡，故拟合效果比较好。

3. 插入排序

（1）算法实现原理

①假设前面n − 1(其中n ≥ 2 )个数已经有序的，现将第n个数插到前面有序序列中，并找到合适位置，使得插入第n 个数后仍为有序序列

②按照此法对所有元素进行插入，直至整个序列为有序序列

（2）源代码

INSERTION-SORT(A)
    for j=2 to A.length:
        key=A[j]
        //将A[j]插入已排序序列A[1..j-1]
        i=j-1
        while i>0 and A[i]>key
            A[i+1]= A[i]
            i=i-1
        A[i+1]=key

下面以使用插入排序3,5,1,2这四个数字为例，以图示介绍插入排序，见下图

（3）算法性能分析

①时间复杂度分析

在插入下标为i的元素的时候（假设该元素为x xx），R_0，R_1，R_2，R_i-1

已经有序了，那么x 实际上有n + 1个备选位置可以插入，按照独立分布来说，每个位置的概率都是 ，那么这n + 1 n+1n+1个位置从左到右对应的比较次数为( i ， i ， i − 1 ， . . . ， 1 )。那么我们就可以得到一趟插入排序的平均时间复杂度为

因此，插入排序的时间复杂度为O (n2)

②数据测试分析

使用随机数生成器生成了从10² 到10²  的不同数据量级的随机数，通过使用插入排序进排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选  10⁵时运行时间为理论值并做表如下：

通过获得的数据，使用10⁵ 时的时间消耗为基准理论值，使用Tableau做图像并拟合如图：

由于插入排序算法时间复杂度为O ( n 2 )，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合O ( n 2 ) 的时间复杂度。

从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍，时间消耗扩大100倍的规律。但对于10¹10²  数量级时存在较大误差，拟合效果较差。通过分析可知，插入排序中进行了对需插入元素的保存操作，当数据较小时，较差的拟合效果是因为每次对插入前数值的保存占用的时间比例较大。当数据较小时，数据交换造成的时间损耗更明显。但当数据变多时，这种影响被冲淡，故拟合效果比较好。

4. 快速排序

（1）算法实现原理

①首先设定一个分界值，通过该分界值将数组分成左右两部分。

②将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

③然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

④重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

下面以使用快速排序11,8,3,9,7,1,2,5这八个数字为例，以图示介绍快速排序，见下图

（2）源代码

QUICKSORT(SeqList R,int low,int high)
  int pivotpos;//划分后的基准记录的位置
  if(low<high)
    //仅当区间长度大于1时才需排序
    pivotpos = Partition(R,low,high);
    //对R[low...high]进行划分
    QuickSort(R,low,pivotpos-1);
    QuickSort(R,pivotpos+1,high);

（3）算法性能分析

①时间复杂度分析：

快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O ( n ) ；而整个快速排序算法的时间复杂度与划分的趟数有关。

最理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log ⁡ n 趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O ( n log ⁡ n )

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n nn的数据表的快速排序需要经过n nn趟划分，使得整个排序算法的时间复杂度为O ( n 2 )

综上快速排序的平均时间复杂度也是O ( n log ⁡ n )

②数据测试分析：

使用随机数生成器生成了从10¹ 到10⁶

的不同数据量级的随机数，通过使用快速排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择10⁵时运行时间为理论值并做表如下

通过获得的数据，使用10⁵ 时的时间消耗为基准理论值，使用Tableau做图像并拟合如图

结合上表和上图不难得出：整体时间消耗都大致满足O ( n log ⁡ n )的时间复杂度，且数据量越大拟合效果越好。

从上表和上图中可以发现整体时间消耗都大致满足时间复杂度。但对于10¹10^2,数量级时存在较大误差，拟合效果较差。通过分析可知，快速排序中开辟申请空间与递归栈都会影响运行性能和运行时间。当数据较小时，这种影响造成的时间损耗更明显。但当数据变多时，开辟空间与递归栈对时间的影响被冲淡，故拟合效果比较好。