8.5_1归并排序-拓冰建站

什么是归并：

把两个或多个有序序列合并成1个

定义3个指针i、j、k，i指向有序序列1当前值，j指向有序序列2当前值，i和j比较大小，小的放在k所指位置上，再让k指针右移和值小的i或j右移

第一轮，i=12，j=7，i>j，把7放在k所指位置，k右移，j右移指向10

第二轮，i=12，j=10，i>j，把10放在k所指位置，k右移，j右移指向21

第三轮，i=12，j=21，i<j，把12放在k所指位置，k右移，i右移指向16

第4轮，i=16，j=21，i<j，把16放在k所指位置，k右移，i右移指向24

第5轮，i=24，j=21，i>j，把21放在k所指位置，k右移，j右移指向24

第6轮，i=24，j=24，i==j，把i指向的24放在k所指位置(也可以让j指向的24放在k所指的位置，两个值相等的元素具体放哪个，可以在代码中定义优先放i的或j的)，k右移，i右移指向33

。。。。。

第9轮，i=45，j指针的指向已经超出j所在序列的数组范围长度，说明j所在序列元素已经被合并完了，则剩余i所在序列元素不用再对比直接把i剩余的元素依次放在k所在序列的表尾当中，合并结束

2路归并：

每选出k指向位置的元素，只需比较i和j所指元素大小，即2路归并每次选k上的元素只需比较1次,实现归并的时候一般使用2路归并实现

4路归并:

4个有序序列即5个指针，每次确定k指针位置上的元素则比较3次。如下先从P1和P2比较选出最小值，假如p2是最小值，即P1>P2，min=P2，再让p2和P3比较，假如P2>P3，则更新min=P3，再让min和P4比较，假如P4<min，则min=P4，即k指向的值为P4，则4路归并需要比较3次。注意每次选的都是最小值，归并的路数越多，需要比较的次数也越多

归并排序手算模拟：

给出一个初始序列(可能无序)，每次合并2个相邻的序列，即每次合并的数组下标都是连续的

第一趟归并，则把每个元素看成已经排好序的单个序列，即把每个元素认为成是1路，第一轮归并会把相邻的2个元素进行2路归并，0和1位置上的元素归并，继续把后边的元素两两相邻的进行2路归并，2和3,4和5归并，最后6位置上的27单出来了，把6归并，相当于27什么也没做

第2趟归并，基于第1趟结果，再次进行相邻的2路归并， 0-1所在块已经有序，2-3所在块有序，把0-1和2-3进行2路归并归并成1个，4-5块和6块已经有序，把这俩再归并成1个序列，经过第2趟归并后，得到2个已经有序的子序列

第3趟归并，基于第2趟的结果2个有序的相邻子序列，再把2个有序的子序列进行2路合并

代码实现：

数组A[]，index为3-6上是有序的，7-9也是有序的，即2个有序子序列相邻，low指针指向最前面元素，mid指针指向第一个有序子序列的最后一个元素，high指针指向第2个有序子序列的最后一个元素，即可以用low、mid、high来指出要合并的2个子序列的范围，即要合并A数组中的low-mid子序列和mid+1-high的子序列，此时这俩序列有序

定义辅助数组B[],大小和A[]相同都为n的长度

merge()中第一个for循环，复制。把A数组的Index为low和high内的元素复制到B数组中，让k指针先指向low，每次把k所指的A数组中的元素复制到B数组中相应位置，每次k++，k<=high，直到k指向high即最后一个要复制的元素时，for循环结束

merge()中第2个for循环，归并。把B数组的2个有序子序列进行归并比较，把较小元素放到A数组位置。i指针指向了B中第1个有序子序列的第1个元素(即i=low)，j指针指向了B中第2个有序子序列的第1个元素(即j=mid+1)，k指向A中的要排序的最前面一个元素(即low指针所在位置k=i)，k所指的位置即是要把i和j中较小的元素放在A数组中的哪个位置。

第一轮，让B数组中的i和j元素比较，i=16，j=21，16<21，则i向右移动i=24，把较小元素放到A数组中k位置即A[k]=B[i++]，k向右移动即k++，此时k在4位置

第2轮，让B数组中的i和j元素比较，i=24，j=21，24>21，则j向右移动j=24，把较小元素放到A数组中k位置即A[k]=B[j++]，k向右移动即k++，此时k在5位置

第3轮，让B数组中的i和j元素比较，i=24，j=24，24==24，代码中用的是B[i]<=B[j],A[k]=B[i++],则当2个有序序列比较的元素相等时，优先让i指针移动，保证了算法的稳定性，因为本来i所在序列就在j所在序列前边。即i向右移动i=37，把较小元素放到A数组中k位置即A[k]=B[i++]，k向右移动即k++，此时k在6位置

第3轮，让B数组中的i和j元素比较，i=37，j=24，37>24，则j向右移动j=33，把较小元素放到A数组中k位置即A[k]=B[j++]，k向右移动即k++，此时k在7位置

第4轮，让B数组中的i和j元素比较，i=37，j=33，37>33，则j向右移动j=33，把较小元素放到A数组中k位置即A[k]=B[j++]，k向右移动即k++，此时k在8位置。下一轮for循环j指向了10的位置，j>high，则在该轮for循环，j<=high不满足条件，跳出for循环

剩下2个while循环判断i和j子序列是否合并完，对于没有合并完的子序列，即B数组中的i或j所在序列，统统放在A数组中所在位置，即每次循环都i++/j++和k++，上边的for循环中j>high了，所以j所在while循环不会执行，i所在循环执行

完整代码：

对无序的数组序列进行归并，从中间把这个数组拆分成2个部分，递归的对左右两个无序序列进行排序，当2个部分排完序之后(最小序列为单个元素是一个序列，2个序列数组下标相邻)即MergeSort()，再对2个有序序列归并即Merge()

A数组要归并排序(A数组元素此时无序)，使用low和high指针指明要归并排序的范围，即low指向最前面元素low=0，high指向最后边一个元素位置high=6，然后把A数组从中间拆分，即mid=(low+high)/2=(0+6)/2=3，然后把A数组一整个序列拆分成左右2个部分，左部分：low~mid，右部分：mid+1~high，对左部分和右部分递归的进行排序，递归排序之后左右部分都能变得有序（咋得到的。。。。。。），比如对左半部分进行排序调用mergeSort()，开始low=0,mid=3=high，第一轮megeSort(A,0,3)，即low=0，high=3，low<high拆分，mid=(0+3)/2=1，第二轮megeSort(A,0,1)，low=0，high=1，low<high则继续拆分，mid=(0+1)/2=0，第3轮megeSort(A,0,0)，low=high=0，则本次递归结束返回上一层，即low=0，high=1，mid=0的一层，调用MergeSort(A,mid+1,high)即MergeSort(A,1,1),即low=1，high=1，则MergeSort右半部分结束MergeSort，回到MergeSort左半部分，即low=0,high=1这一层，即开始执行Merge(A,low,mid,high)，此时low=0,mid=0,high=1，开始对这两个最短子序列进行归并，即对A数组中的0和1进行归并，即实际拆分成一个个相邻元素序列后进行归并，即把只含有一个元素的2个有序子序列进行归并，则先把A数组中的2个元素49和38复制到B数组中，在B数组中对这2个有序子序列元素进行归并，每次归并后都把较小元素写回到A数组k位置，即把38和49进行归并排序了，则得到2个有序子序列之后，再对2个有序子序列进行归并

算法效率分析：

时间复杂度：

是O(nlog2n)

树高是h，则归并排序的趟数是h-1趟，因为2路归并可以看成是一个归并树，所以二叉树第h层的最多有2的h-1次方个节点即n<=2的h-1次方，对数求解为h-1=log2n向上取整，即n个元素进行归并排序，归并趟数为log2n向上取整，每趟归并的时间复杂度为O(n)【为啥是O(n)不是O(1)，每次不就2个元素进行比较吗，注意一趟的比较不是就比较2个元素，而是比较2个或多个左右部分序列，2个或多个左右序列构成了整个数组序列，即数组长度n】，则算法时间复杂度为O(nlog2n)。如下图假设要进行第3趟排序(最后一趟对比应该是对比次数最多)，即要把第2趟结果2个有序的子序列合并成1个，让i指针和j指针指向2个序列的最小的元素，每对比关键字1次，就可以挑出2个序列中更小的元素，即每对比一次就可以从这俩序列的剩余元素中挑出最小的一个，则让2个有序序列合并成1个所要对比的关键字次数<=n-1次，即数量级为O(n)，第一趟归并，是2个元素之间两两互相对比，数组长度为n，两两元素对比，则要对比的次数总和为n/2，数量级也为O(n)，即每趟归并的时间复杂度都是O(n)数量级

不管归并排序开始给的序列是有序还是无序，最终时间复杂度都是O(nlog2n)，因为无序或有序吧，在最后一趟归并排序时都是2个有序序列归并，2个有序序列归并都是O(n)，即使是无序，在第一趟归并时，比较次数是n/2其数量级也是O(n)，最后都是O(nlog2n)，即归并排序的最好最坏和平均时间复杂度都是O(nlog2n)