一、实验目的与要求

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均达到最小值

$$C_{min}=n-1$$

$$M_{min}=0$$

所以，冒泡排序最好的时间复杂度为$O(n)$
若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较$(1\le i\le n-1)$，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
$$C_{max}=\frac{n(n-1)}{2}=O(n^2)$$
$$M_{max}=\frac{3n(n-1)}{2}=O(n^2)$$

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

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

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.000160	-3.795880017	0.000123	-3.9102255
$10^2$	0.006225	-2.205860644	0.0122963	-1.9102255
$10^3$	0.572565	-0.242175203	1.22963	0.08977445
$10^4$	102.0520	2.00882152	122.963	2.08977445
$10^5$	12296.30	4.08977445	12296.3	4.08977445
$10^6$	1236880	6.092327567	1229630	6.08977445

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

   由于冒泡排序算法时间复杂度为$O(n^2)$，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合$O(n^2)$的时间复杂度。
  从上图可知，实际时间消耗曲线与理论时间消耗基本拟合，冒泡排序算法的时间复杂度满足$O(n^2)$。

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$与$n-1$次之间。选择排序的比较操作为$n(n-1)/2$ 次之间。选择排序的赋值操作介于 $0$ 和 $3(n-1）$ 次之间。比较次数为$O(n^2)$。比较次数与关键字的初始状态无关，总的比较次数$N=(n-1)+(n-2)+...+1=n(n-1)/2$。
交换次数$O(n)$，最好情况是，已经有序，交换0次；最坏情况交换$n-1$次，逆序交换$n/2$次。因此选择排序的时间复杂度为$O(n^2)$

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

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.00011	-3.958607315	0.00002544	-4.5944829
$10^2$	0.003785	-2.421934116	0.002544	-2.5944829
$10^3$	0.325995	-0.486789061	0.2544	-0.5944829
$10^4$	29.286	1.466660058	25.544	1.40728891
$10^5$	2554.4	3.407288906	2554.4	3.40728891
$10^6$	257163	5.410208483	255440	5.40728891

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

由于选择排序算法时间复杂度为$O(n^2)$，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合$O(n^2)$的时间复杂度。
从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍，时间消耗扩大100倍的规律。但对于$10^1,10^2$数量级时存在较大误差，拟合效果较差。通过分析可知，选择排序中进行了很多次相互调换元素（相互赋值）的操作，从而造成了时间浪费。我进行了如下两次对比实验，使用库函数swap和手写调换元素的函数进行对比，可以发现，使用swap函数的小数据拟合效果要明显好于手写。因此，小数据下，较差的拟合效果是因为较多次交换占用了更多时间，当数据较小时，数据交换造成的时间损耗更明显。但当数据变多时，这种影响被冲淡，故拟合效果比较好。

3. 插入排序

（1）算法实现原理
①假设前面$n-1$(其中$n\ge 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$），$R_0,R_1,R_2\cdots R_{i-1}$已经有序了，那么$x$实际上有$n+1$个备选位置可以插入，按照独立分布来说，每个位置的概率都是$\frac{1}{i+1}$，那么这$n+1$个位置从左到右对应的比较次数为$(i，i，i-1，...，1)$。那么我们就可以得到一趟插入排序的平均时间复杂度为$$\frac{1}{i+1}(\sum _{j=1}^{i}j+1)=\frac{1}{i+1}\sum _{j+1}^{i}j+\frac{i}{i+1}=\frac{i}{2}+1-\frac{1}{i+1}$$ 接下来，我们对$n-1$趟结果进行求和，得到最终时间复杂度为：
$$T(n)=\sum _{i=1}^{n-1}(\frac{i}{2}+1-\frac{1}{i-1})=\frac{(n+1)(n-4)}{4}-\sum _{j=1}^n\frac{1}{j}\approx \frac{(n+1)(n-4)}{4}-{\int }_1^n\frac{1}{x}dx\le \frac{(n+1)(n-4)}{4}-\ln n=O(n^2)$$
因此，插入排序的时间复杂度为$O(n^2)$

②数据测试分析
使用随机数生成器生成了从${10}^1$到${10}^6$的不同数据量级的随机数，通过使用插入排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择${10}^5$时运行时间为理论值并做表如下：

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.00005	-4.30102	9.7215E-06	-5.0122667
$10^2$	0.001455	-2.8371	0.00097215	-3.0122667
$10^3$	0.12225	-0.912751132	0.097215	-1.0122667
$10^4$	10.2027	1.008715117	9.7215	0.98773328
$10^5$	972.15	2.987733281	972.15	2.98773328
$10^6$	95403.5	4.9795643	97215	4.9877

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

由于插入排序算法时间复杂度为$O\left(n^2\right)$，故，数量级扩大10倍时，时间消耗应扩大100倍。由上图，可得随着数据量的增大，拟合效果越好，所有实验数据符合$O\left(n^2\right)$的时间复杂度。
从上表和上图中可以发现整体时间消耗都大致满足数量级扩大10倍，时间消耗扩大100倍的规律。但对于${10}^1,{10}^2$数量级时存在较大误差，拟合效果较差。通过分析可知，插入排序中进行了对需插入元素的保存操作，当数据较小时，较差的拟合效果是因为每次对插入前数值的保存占用的时间比例较大。当数据较小时，数据交换造成的时间损耗更明显。但当数据变多时，这种影响被冲淡，故拟合效果比较好。

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$的数据表的快速排序需要经过$n$趟划分，使得整个排序算法的时间复杂度为$O(n^2)$。
综上快速排序的平均时间复杂度也是$O(n\log n)$。
②数据测试分析：
使用随机数生成器生成了从${10}^1$到${10}^6$的不同数据量级的随机数，通过使用快速排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择${10}^5$时运行时间为理论值并做表如下

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.00008	-4.0969	0.0001	-3.93781301
$10^2$	0.00102	-2.991399828	0.0023079	-2.63678301
$10^3$	0.033025	-1.481157174	0.0346185	-1.46069175
$10^4$	0.48912	-0.310584579	0.46158	-0.33575302
$10^5$	5.76975	0.76115699	5.76975	0.761156
$10^6$	67.6157	1.8300	69.237	1.8403

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

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

5. 合并排序

（1）算法实现原理
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
下面以使用合并排序14,12,15,13,11,16这六个数字为例，以图示介绍合并排序，见下图

（2）源代码

//2、合并化
MERGE(sourceArr,tempArr,sIndex,midIndex,eIndex)
    i = sIndex
    j = midIndex+1
    k = sIndex
//取出两个有序子序列中最小的一个元素，放入新的有序数列中
    while i! = midIndex+1 and j!=eIndex+1
        if sourceArr[i] < sourceArr[j]
            tempArr[k] = sourceArr[i]
            i++
        else
            tempArr[k] = sourceArr[j]
            j++
        k++
//前面的有序数列中还有元素
    while i != midIndex+1
        tempArr[k++] = sourceArr[i++]
//后面的有序数列还有元素
    while j != eIndex+1
        tempArr[k++] = sourceArr[j++]
//将有序数列拷贝给原数列
    for m = sIndex to eIndex
        sourceArr[m] = temp[m]
 
//1、归一化
MERGESORT(sourceArr,tempArr,sIndex,eIndex)
    //类似二分查找一样，每次取半
    if sIndex < eIndex
       mid = sIndex + (eIndex - sIndex)/2
       MERGESORT(sourceArr,tempArr,sIndex,mid)
       MERGESORT(sourceArr,tempArr,mid+1,eIndex)
       MERGE(sourceArr,tempArr,sIndex,mid,eIndex)

（3）算法性能分析
①时间复杂度分析：
不妨假设一个序列有$n$个数的排序时间为$T(n)$，$T(n)$是一个关于$n$的函数，随着$n$的变化而变化。
那么我们将$n$个数的序列，分为两个$\frac{n}{2}$的序列。则有：
$$T(n)=2\ast T(\frac{n}{2})+t(t为合并时间)$$
由于合并时，两个子序列已经组内排好序了，那我们将两个排好序的序列组合成一个大的有序序列，只需要一个if循环即可。if循环中有n个数需要比较，所以时间复杂度为n。则有：
$$T(n)=2\ast T(\frac{n}{2})+n$$
我们再将两个$\frac{n}{2}$的序列再分成4个$\frac{n}{4}$的序列。则有：
$$T(\frac{n}{2})=2\ast T(\frac{n}{4})+\frac{n}{2}$$
代入并化简得：
$$T(n)=4\ast T(\frac{n}{4})+2n$$$$\dots \dots$$
不难求得，整体时间消耗有如下表达式：
$$T\left(n\right)=n\ast {\log }_{2}n$$
综上，合并排序的时间复杂度为$$O\left(n\ast \log n\right)$$

②数据测试分析
使用随机数生成器生成了从${10}^1{10}^6$的不同数据量级的随机数，通过使用合并排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择${10}^5$时运行时间为理论值并做表如下

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.00202	-2.6946	0.000276336	-3.55856253
$10^2$	0.010675	-1.971632116	0.00552672	-2.25753254
$10^3$	0.16485	-0.782911049	0.0829008	-1.08144128
$10^4$	1.42697	0.154414843	1.105344	0.043497458
$10^5$	13.8168	1.140407471	13.8168	1.140407471
$10^6$	159.301	2.202218502	165.8016	2.219588717

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

结合以上表以及上图不难得出：整体时间消耗都大致满足$O\left(n\log n\right)$的时间复杂度。但对于${10}^1,{10}^2$两组数据存在较大偏差。这是因为合并排序需要额外的临时空间辅助，有一定的资源损耗，且当数据量较小时，资源损耗的影响将变得显著。从一定程度上导致，实际时间会大于理论时间。当数据量较大且运行时间变长时，拟合效果比较好。

6. 基数排序

（1）算法实现原理
①将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
②然后，从最低位开始，进行一次排序。
③从第二低位进行一次排序
④依次按照以上排序方法从最低位一直到最高位排序完成后, 数列就变成有序序列。

下面以使用基数排序123,156,945,624,464,32这六个数字为例，以图示介绍基数排序，见下图

（2）源代码

RADIXSORT(A,d)
	for i = 1 to d
		use a stable sort to sort array A on digit i

（3）算法性能分析

①时间复杂度分析：
基数排序的时间复杂度是$O(k\cdot n)$，其中n是排序元素个数，$k$是数字位数。$k$的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小； $k$决定了进行多少轮处理，而$n$是每轮处理的操作数目。
以排序$n$个不同整数来举例，假定这些整数以$B$为底，这样每位数都有$B$个不同的数字，$k={\log }_{B}N$,$N$是待排序数据类型全集的势。虽然有$B$个不同的数字，需要$B$个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均$n$次操作来把整数放到合适的桶中去，所以就有：
$$k\approx {\log }_{B}N$$

所以，基数排序的平均时间T就是：
$$T\approx n\ast {\log }_{B}N$$

②数据测试分析
使用随机数生成器生成了从$10^1$到$10^6$的不同数据量级的随机数，通过使用基数排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择$10^5$时运行时间为理论值并做表如下：

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	0.000515	-3.288192771	8.41192E-05	-4.07510487
$10^2$	0.0025	-2.602059991	0.001682384	-2.77407487
$10^3$	0.029865	-1.524837481	0.02523576	-1.59798361
$10^4$	0.28812	-0.54042659	0.336476	-0.47304487
$10^5$	4.20596	0.623865138	4.20596	0.623865138
$10^6$	50.7379	1.705332	50.47152	1.7030463

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

结合上图表不难得出：整体时间消耗都大致满足$O(n\log n)$的时间复杂度。但对于$10^1,10^2$两组数据存在较大偏差。这是因为当数据量较小时，基数排序对较少位数进行排序时内存消耗较大，比较交换次数多，且需要对每一基数进行收集排序，一定程度上导致了时间的增加。当数据量较大且运行时间变长时拟合效果较好。

7. 希尔排序

（1）算法实现原理
①选择一个增量序列$t_1，t_2，\dots \dots ，t_k$，其中 $t_i>t_j,t_k=1$；
②按增量序列个数$k$，对序列进行$k$趟排序；
③每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$m$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。
下面以使用冒泡排序49,38,65,97,76,13,27,49,55,4这十个数字为例，以图示介绍希尔排序，见下图

（2）源代码

SHELLSORT(A)
input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:    
    for i = inc .. n − 1 do:   
        temp ← a[i]        
        j ← i        
        while j ≥ inc and a[j − inc] > temp do: 
            a[j] ← a[j − inc]  
            j ← j − inc        
        a[j] ← temp    
    inc ← round(inc / 2)

（3）算法性能分析
①时间复杂度分析：
  与其他算法相比，希尔排序并没有实际确定的时间复杂度，其时间复杂度与步长序列的选取有很大关系。
  例如当选择不同步长序列时，有如下时间复杂度关联表：

步长序列	时间复杂度
$\frac{n}{2^i}$	$O\left(n^2\right)$
$2^k-1$	$O\left(n^{\frac{3}{2}}\right)$
$2^i\ast 3^j$(时间复杂度最小)	$O\left(n\ast {\log }^{2}n\right)$

②数据测试分析
使用随机数生成器生成了从${10}^1$到${10}^6$的不同数据量级的随机数，通过使用希尔排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，做表如下：

数据量级	平均时间(ms)	平均时间对数
$10^1$	6.00E-05	–4.22184875
$10^2$	0.0012	-2.920818754
$10^3$	0.05229	-1.281581358
$10^4$	0.742845	-0.129101795
$10^5$	9.70846	0.987150346
$10^6$	133.547	2.125634136

通过获得的数据，使用Tableau做图像如图：

从上表和上图中可以发现整体图像成直线大致符合理论的时间复杂度。

8. 堆排序

（1）算法实现原理
①创建一个初始堆H
②把堆首（最大值）和堆尾互换；
③把堆的尺寸缩小 1，并调整堆。
④重复②，直至堆的大小为1

下面以使用堆排序4,5,3,0,1,7,2,6这八个数字为例，以图示介绍堆排序，见下图

以上即为堆排序中一次调整的过程，当调整完一次后，使堆的大小减一，并重新调整堆，直至最后堆的大小为1，即可完成排序。

（2）源代码

HEAP-SORT(A):
    BUILD-MAX-HEAP(A);     //构建最大堆
    for i = A.length downto 2:
        exchange A[i] and A[1];
        A.heap-size = A.heap-size-1;
        MAX-HEAPIFY(i);

构建大顶堆伪代码：
BUILD-MAX-HEAP(A):
    A.heap-size = A.length;
    //heap-size代表整个数组中在堆中的元素个数
    for i = A.length/2 downto 1:
        MAX-HEAPIFY(i)

维护大顶堆伪代码：
MAX-HEAPIFY(A, i):        //维护堆性质的关键， 用于检测是否满足堆的性质
    l = left(i);
    r = right(i);   //记录左右孩子的下标
    if l <=  A.heap-size and A[l] >= A[i]:
        largest = l;    //记录根节点和左右孩子中最大数的下标
    else :
        largest = r;
    
    if r <= A.heap-size and r >= A[largest]:
        largest = r;
    
    if i != largest:
        exchange A[i] and A[largest];
        MAX-HEAPIFY (A, largest);

（3）算法性能分析
①时间复杂度分析：
  堆排序的排序过程主要分为构建初始堆和进行排序两部分，接下来分别进行时间复杂度分析：
a.初始化建堆：
  初始化建堆只需要对二叉树的非叶子节点调用调整堆函数，由下至上，由右至左选取非叶子节点来进行调整。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。
  假设高度为$k$，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的则无需交换）；倒数第三层则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
那么总的时间计算为：
$$T=(k-i)2^{i-1}$$
  其中$i$ 表示第几层，$2^{i-1}$表示该层上元素个数，$k-i$表示子树上要下调比较的次数。则有：
$$T=1\ast 2^{k-2}+2\ast 2^{k-3}+3\ast 2^{k-4}\cdots \cdots +\left(k-1\right)2^0$$
$$T=2^k-k-1$$
又因为$k$为完全二叉树的深度，则有$k=\log n$，把此式带入得：
$$T=n-\log n-1$$
则堆排序初始堆的时间复杂度为：$O\left(n\right)$

b. 排序重建堆
在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重建，只需对堆的顶点调用调整堆函数。
每次重建意味着有一个节点出堆，所以需要将堆的容量减一。调整堆函数的时间复杂度$k=\log n$，$k$为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要$n-1$次循环，每次循环的比较次数为$\log i$，则有：
$$T=\log 2+\log 3+\cdots \cdots +\log n-1+\log n=\log n!$$
又因为
$${\left(\frac{n}{2}\right)}^2\le n!\le n^2$$
则有：
$$\frac{n}{4}\ast \log n\le \frac{n}{2}\log \frac{n}{2}\le \log n!\le n\log n$$
即$\log n!$与$n\log n$是同阶函数：
　　
　则堆排序的时间复杂度为$O\left(n\log n\right)$

②数据测试分析：
使用随机数生成器生成了从${10}^1$到${10}^6$的不同数据量级的随机数，通过使用堆排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择${10}^5$时运行时间为理论值并做表如下：

数据量级	平均时间(ms)	平均时间对数	理论值(ms)	理论值对数
$10^1$	7.50E-05	-4.124938737	0.000197032	-3.7054628
$10^2$	0.003155	-2.501000636	0.003940644	-2.4044328
$10^3$	0.057635	-1.239313703	0.05910966	-1.2283415
$10^4$	0.803985	-0.094752054	0.7881288	-0.1034028
$10^5$	9.85161	0.993507211	9.85161	0.99350721
$10^6$	125.718	2.099397463	118.2193	2.072688

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

  结合以上图标图不难得出：整体时间消耗都大致满足$O\left(n\log n\right)$的时间复杂度。但对于${10}^1,{10}^2$两组数据存在较大偏差。通过对算法进行分析不难得出，这两组时堆排序的运行时间过短。主要运行时间来自于生成初始堆以及内存开辟而不是进行排序，因此，时间会略大于理论值。
  当数据较大时，主要时间消耗来自于排序的时间消耗，故拟合效果较好。

（二）多种算法性能比较

我们分别对每个算法的效率以及实现方法探究完毕后，不禁产生如下疑问：对于不同数量级的数据，应该如何选择算法，以更高效的完成排序呢？为探究如上问题，特进行如下实验：
对于以上八种排序算法，分别进行从${10}^1$到${10}^6$数量级的20次测试，分别以时间消耗值和时间消耗对数值做表如下：

数量级	选择排序	冒泡排序	插入排序	快速排序	合并排序	基数排序	希尔排序	堆排序
${10}^1$	0.00011	0.00016	0.00005	0.00008	0.00202	0.00052	0.00006	0.00008
${10}^2$	0.00379	0.00623	0.00146	0.00102	0.01068	0.0025	0.0012	0.00316
${10}^3$	0.326	0.57257	0.12225	0.03303	0.16485	0.02987	0.05229	0.05764
${10}^4$	29.286	102.052	10.2027	0.48912	1.42697	0.28812	0.74285	0.80399
${10}^5$	2554.4	12296.3	972.15	5.76975	13.8168	4.20596	9.70846	9.85161
${10}^6$	257163	1236880	95403.5	67.6157	159.301	50.7379	133.547	125.718

为了分析各数值间对比关系，对数据进行可视化处理，以时间消耗对数值做折线图如下：

  可以看到，对于数量级很小时除基数排序与合并排序外的六种排序方式都比较省时间。当数量级界于${10}^2$到${10}^3$之间时，八种排序算法的时间消耗差距不大。但当数据量较大时，基数排序，快速排序，合并排序和堆排序有明显的优势。而冒泡排序，选择排序和插入排序则需要消耗较多的时间完成排序操作。
  对于较少数据量级时，插入排序表现出了很优秀的性能，甚至比快速排序还要快，这是因为与快速排序相比：
  ①插入排序没有额外内存的申请和释放开销
  ②插入排序没有递归栈的开销

  对于时间复杂度同为$O\left(n^2\right)$的插入排序，选择排序和冒泡排序而言，对于整个${10}^1$~${10}^6$的数量级均有插入排序时间最短，冒泡排序时间最长。这是由于冒泡排序中比较次数的时间复杂度为$O\left(n^2\right)$，且只要顺序相反，就需要对两个数的顺序进行调换，产生很多次中间的不必要调换操作，从而延长了运行所需时间。
  选择排序和插入排序相比较，插入排序更快。其主要原因可能为选择排序需要从序列中找到当前最大或最小的值才能进行排序，因此每次都需要与子序列中的全部元素进行比较。而插入排序无需比较子序列全部元素，只需要找到当前序列第一个比自己大或小的元素，将自身插入到其前一个位置即可。因此插入排序的时间略小于选择排序。

  对于其他五个时间复杂度为$O\left(n\ast \log n\right)$的排序算法，快速排序出现最差的情况并不是由于输入数据，而是选取到的随机数本身，选到极端的情况非常小，所以对于绝大部分数据而言都是能达$O\left(n\ast \log n\right)$，而合并排序需要较多赋值的语句，受输入数据的影响比较大，因此当数据规模较大时，不受输入数据影响的快速排序快于合并排序。对于堆排序，实现过程中需要反复调整堆的结果，赋值调整的次数也较多，因此时间消耗也相对较大。而基数排序只对各个数位进行排序，大大缩减了排序所需的时间，因而时间消耗最小。

  对于整体八种算法，不难看出，对于数据量较小时，时间复杂度为$O\left(n^2\right)$的算法与时间复杂度为$O\left(n\ast \log n\right)$的算法区别不大，都能较好的完成排序。而当数据量较大时，时间复杂度为$O\left(n\ast \log n\right)$的算法体现出明显优势，与时间复杂度为$O\left(n^2\right)$的算法相比节省了很多时间。因此当数据量较小时，可以选择除基数排序与合并排序外的六种排序方式进行排序。但当数据量较大时，则应该选择基数排序或快速排序进行排序操作。

（三）实验算法源码分析

详细的完整代码在附件中。
现对代码结构及实现过程进行如下解释：
1、L1~L9：
进行头文件声明

2、L11~L242：
定义各个排序函数，每个函数的实现过程中均包含详细的注释。

3、L261~L558：
主函数：
①使用输出流创建文件，将每次程序运行的结果存入details.txt和result.txt中

②对于每个算法，利用循环将数据量级从${10}^1$~${10}^6$进行测试，每次测试时，均生成20组数据，计算时间后将结果再存会result.txt和details.txt文件中。

四、实验结论或体会

①同样问题下不同的数量级有不同的处理方法并应选择不同的算法。
例如对${10}^1{10}^3$这种小数据的排序可以选择基数排序与合并排序外的六种排序方式。而对数据量大于${10}^4$的数据应该选择快速排序，合并排序，基数排序，希尔排序或堆排序。对于数据量巨大例如${10}^{12}$的数据则应该选择计数排序，并应该考虑内存外存的数据搬运问题。

②既定算法是对某种普遍情况的处理方式，可能存在极端情况。
例如快速排序，当数据大小大致成二分分布时，有很好的性能，但当数据恰好倒序或恰好正序时，则性能很差。因此对于特殊情况需要选择特定算法进行处理。
③不能忽略对现有算法的优化
例如冒泡排序和选择排序，在算法进行中，存在冗余操作，即存在可优化的空间。对算法进行优化可以在算法本质不变的情况下一定程度上提高算法的效率。
④实践是检验算法的唯一标准，应避免“想当然”
例如两种“可行”的冒泡排序优化算法，从理论上都似乎可行，但实际运行起来，一种算法并不能提高运行效率反而降低了效率。这给我的启示是对于算法的学习中，一定要使用数据对算法进行实践，避免理论上的想当然。

五、思考

在本次实验过程中，我也发现了一些问题如下：

1. 冒泡排序算法优化
  传统冒泡排序算法中，排序完成的结束标准为所有循环全部循环结束。在实际算法运行中，会发现，在某次排序之后，部分序列变为有序，此时这部分序列不需进行冒泡排序。基于此，提出如下两个优化算法：
①减少无效循环次数
  不难发现在实际运行中，冒泡排序算法截止的标志是全部循环运行结束，因此可能存在在循环结束前，序列已经有序，但仍需进行循环，此时将造成时间浪费。可以通过定义标志变量判断冒泡的一趟是否进行交换，如果未进行交换则序列已经有序，break出循环减少无效循环。基于这个想法，编写代码并测试：

数据量级	优化前时间	优化后时间
${10}^1$	0.000160	0.000180
${10}^2$	0.006225	0.007125
${10}^3$	0.572565	0.76642
${10}^4$	102.0520	124.5146
${10}^5$	12296.30	15131.16
${10}^6$	1236880	1578391

  从上表中可以发现，“优化”过的算法时间不仅没有减少，反而增加了。可能是因为算法几乎要全部循环结束才能完成排序，设置标志变量减少的循环次数不多。而且对标志变量赋值判断消耗的时间大于设置标志变量减少的循环消耗时间。因此不能提高算法效率！

②提高有效循环效率
  假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了
  基于这个想法，编写代码并测试

数据量级	优化前时间	优化后时间
${10}^1$	0.000160	0.000140
${10}^2$	0.006225	0.005115
${10}^3$	0.572565	0.5139
${10}^4$	102.0520	98.5638
${10}^5$	12296.30	11984.69
${10}^6$	1236880	1204031

可以看出，冒泡排序的时间消耗略微缩短了，算法得到了优化。

2.选择排序算法优化
  在正常的选择排序中，每次都需要对所有元素进行比较但仅获得最大/最小值，不妨在选择排序过程中，每次获得最大值和最小值，从而将选择次数缩短一半。
  基于此想法，编写代码并测试

数据量级	优化前时间	优化后时间
$10^1$	0.00011	0.00009
$10^2$	0.003785	0.003281
$10^3$	0.325995	0.291534
$10^4$	29.286	26.1481
$10^5$	2554.4	2198.9
$10^6$	257163	201919

可以看出，选择排序的时间消耗明显缩短，大致节省了20%的时间，算法得到了优化。

3.（思考题）现在有1万亿的数据，请选择合适的排序算法与数据结构，在有限的时间内完成进行排序。

一万亿数据进行排序即对${10}^{12}$个整数进行排序。一个长整形占4个字节。则${10}^{12}$个整数占$4\times {10}^{12}$B$\approx 4$TB。如此巨大的数据量不可能一次放到内存中。因此需要将数据存放在外存中，并在内存外存中搬运数据完成数据的排序处理。
此时，一般的排序方法将由于无法使用，经过查阅资料后，我选择了一种非比较算法进行排序——计数排序。
（1）计数排序介绍与原理
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为$O(n+k)$（其中k是整数的范围），快于任何比较排序算法。
算法具体实现如下：
①开辟一新数组，用来作为桶存每个元素出现的频率
②遍历待排序序列，将每个元素放入对应的桶中（频率值加一）
③遍历频率数组，并将每个元素存回原序列。
下面以排序2,3,8,4,6,1,3,9,4,7这10个数为例

（2）计数排序伪代码

COUNTSORT(A):
    memset(C,sizeof(C),0);       //C数组置零    
for i=1 to n do    
    C[A[i]]++;               //统计输入数组中相同元素的个数    
for i=2 to k do    
    C[i] = C[i]+C[i-1];       //C[i]表示输入数组中小于或者等于i的元素个数    
for i=n downto 1 do    
    B[C[A[i]]] = A[i];       //把每一个A[i]放到输出数组中相应位置上    
    C[A[i]]--;             //如果有几个相同元素时,当然不能放在同一个位置了。

（3）计数排序在相对小数量级下的测试（单位ms）
通过随机数生成器生成不同测试数据，分别使用计数排序和通过实验得出对于大数据最高效的基数排序进行排序并比较时间。

数据量级	基数排序时间消耗	计数排序时间消耗
$10^1$	0.000515	0.00032
$10^2$	0.0025	0.00066
$10^3$	0.029865	0.00432
$10^4$	0.28812	0.06746
$10^5$	4.20596	0.78152
$10^6$	50.7379	9.81722
$10^7$	609.548	173.873
$10^8$	7111.39	2154.45
$10^9$	81273.1	30035.6

可以看出，计数排序的时间消耗比目前最快的算法仍要快出很多。

（4）具体排序${10}^{12}$数据的步骤
①利用文件流创建若干个空文件，用来作为桶存各个数字出现频率。
②利用文件流，从外存中读入数字。并放入桶文件的对应位置。
③清空原数据源文件，并遍历桶文件将对应数字存入数据源文件中。

（5）时间消耗预计
由于计数排序的时间复杂度为$O(n+k)$（其中k是整数的范围）。则当排序${10}^{12}$个数字时，大约需要$17h$