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 nn个数的排序时间为T ( n )，T ( n )是一个关于n 的函数，随着n 的变化而变化。
那么我们将n 个数的序列，分为两个
的序列。则有：
由于合并时，两个子序列已经组内排好序了，那我们将两个排好序的序列组合成一个大的有序序列，只需要一个if循环即可。if循环中有n个数需要比较，所以时间复杂度为n。则有：
②数据测试分析
使用随机数生成器生成了从101106的不同数据量级的随机数，通过使用合并排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择105时运行时间为理论值并做表如下
通过获得的数据，使用106 时的时间消耗为基准理论值，使用Tableau做图像并拟合如图：
结合以上表以及上图不难得出：整体时间消耗都大致满足O ( n log n ) 的时间复杂度。但对于101102两组数据存在较大偏差。这是因为合并排序需要额外的临时空间辅助，有一定的资源损耗，且当数据量较小时，资源损耗的影响将变得显著。从一定程度上导致，实际时间会大于理论时间。当数据量较大且运行时间变长时，拟合效果比较好。
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 ⋅ n )，其中n是排序元素个数，k kk是数字位数。k kk的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小； k 决定了进行多少轮处理，而n nn是每轮处理的操作数目。
以排序n nn个不同整数来举例，假定这些整数以B 为底，这样每位数都有B 个不同的数字，k = log B N,N待排序数据类型全集的势。虽然有B 个不同的数字，需要B 个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均n 次操作来把整数放到合适的桶中去，所以就有：
②数据测试分析
使用随机数生成器生成了从 101到106的不同数据量级的随机数，通过使用基数排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择105时运行时间为理论值并做表如下：
通过获得的数据，使用 105时的时间消耗为基准理论值，使用Tableau做图像并拟合如图
结合上图表不难得出：整体时间消耗都大致满足O ( n log n )的时间复杂度。但对于
两组数据存在较大偏差。这是因为当数据量较小时，基数排序对较少位数进行排序时内，101102存消耗较大，比较交换次数多，且需要对每一基数进行收集排序，一定程度上导致了时间的增加。当数据量较大且运行时间变长时拟合效果较好。
7. 希尔排序
（1）算法实现原理
①选择一个增量序列t 1 ， t 2 ， … … ， t k，其中 t i > t j , t k = 1
②按增量序列个数k kk，对序列进行k kk趟排序；
③每趟排序，根据对应的增量t1 ，将待排序列分割成若干长度为m mm的子序列，分别对各子表进行直接插入排序。仅增量因子为1 11时，整个序列作为一个表来处理，表长度即为整个序列的长度。
下面以使用冒泡排序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）算法性能分析
①时间复杂度分析：
与其他算法相比，希尔排序并没有实际确定的时间复杂度，其时间复杂度与步长序列的选取有很大关系。
例如当选择不同步长序列时，有如下时间复杂度关联表：
②数据测试分析
使用随机数生成器生成了从 101到102
的不同数据量级的随机数，通过使用希尔排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，做表如下：
通过获得的数据，使用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 kk，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的则无需交换）；倒数第三层则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
那么总的时间计算为：
则堆排序初始堆的时间复杂度为：O ( n )
b. 排序重建堆
在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重建，只需对堆的顶点调用调整堆函数。
每次重建意味着有一个节点出堆，所以需要将堆的容量减一。调整堆函数的时间复杂度k = log，k 为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要n − 1次循环，每次循环的比较次数为log i ，则有：
即log n ! 与n log n 是同阶函数：
则堆排序的时间复杂度为O ( n log n )
②数据测试分析：
使用随机数生成器生成了从
101到106的不同数据量级的随机数，通过使用堆排序进行排序并获取了程序运行时间。为降低偶然性，对20组数据取平均值，选择105时运行时间为理论值并做表如下
通过获得的数据，使用105时的时间消耗为基准理论值，使用Tableau做图像并拟合如图：
结合以上图标图不难得出：整体时间消耗都大致满足O ( n log n ) )的时间复杂度。但对于101,102两组数据存在较大偏差。通过对算法进行分析不难得出，这两组时堆排序的运行时间过短。主要运行时间来自于生成初始堆以及内存开辟而不是进行排序，因此，时间会略大于理论值。
当数据较大时，主要时间消耗来自于排序的时间消耗，故拟合效果较好。
（二）多种算法性能比较
我们分别对每个算法的效率以及实现方法探究完毕后，不禁产生如下疑问：对于不同数量级的数据，应该如何选择算法，以更高效的完成排序呢？为探究如上问题，特进行如下实验：
对于以上八种排序算法，分别进行从10 1到10 6数量级的20次测试，分别以时间消耗值和时间消耗对数值做表如下：
为了分析各数值间对比关系，对数据进行可视化处理，以时间消耗对数值做折线图如下：
可以看到，对于数量级很小时除基数排序与合并排序外的六种排序方式都比较省时间。当数量级界于102到 103之间时，八种排序算法的时间消耗差距不大。但当数据量较大时，基数排序，快速排序，合并排序和堆排序有明显的优势。而冒泡排序，选择排序和插入排序则需要消耗较多的时间完成排序操作。
对于较少数据量级时，插入排序表现出了很优秀的性能，甚至比快速排序还要快，这是因为与快速排序相比：
①插入排序没有额外内存的申请和释放开销
②插入排序没有递归栈的开销
对于时间复杂度同为O ( n 2 ) 的插入排序，选择排序和冒泡排序而言，对于整个101~106
的数量级均有插入排序时间最短，冒泡排序时间最长。这是由于冒泡排序中比较次数的时间复杂度为O ( n 2 ) O，且只要顺序相反，就需要对两个数的顺序进行调换，产生很多次中间的不必要调换操作，从而延长了运行所需时间。
选择排序和插入排序相比较，插入排序更快。其主要原因可能为选择排序需要从序列中找到当前最大或最小的值才能进行排序，因此每次都需要与子序列中的全部元素进行比较。而插入排序无需比较子序列全部元素，只需要找到当前序列第一个比自己大或小的元素，将自身插入到其前一个位置即可。因此插入排序的时间略小于选择排序。
对于其他五个时间复杂度为O ( n ∗ log n ) 的排序算法，快速排序出现最差的情况并不是由于输入数据，而是选取到的随机数本身，选到极端的情况非常小，所以对于绝大部分数据而言都是能达O ( n ∗ log n )，而合并排序需要较多赋值的语句，受输入数据的影响比较大，因此当数据规模较大时，不受输入数据影响的快速排序快于合并排序。对于堆排序，实现过程中需要反复调整堆的结果，赋值调整的次数也较多，因此时间消耗也相对较大。而基数排序只对各个数位进行排序，大大缩减了排序所需的时间，因而时间消耗最小。
对于整体八种算法，不难看出，对于数据量较小时，时间复杂度为O ( n 2 )的算法与时间复杂度为O ( n ∗ log n ) O的算法区别不大，都能较好的完成排序。而当数据量较大时，时间复杂度为O ( n ∗ log n ) 的算法体现出明显优势，与时间复杂度为O ( n 2 ) 的算法相比节省了很多时间。因此当数据量较小时，可以选择除基数排序与合并排序外的六种排序方式进行排序。但当数据量较大时，则应该选择基数排序或快速排序进行排序操作。
