数据结构基础之《（9）—归并排序》

一、什么是归并排序

1、整体是递归，左边排好序+右边排好序+merge让整体有序
2、让其整体有序的过程里用了排外序方法
3、利用master公式来求解时间复杂度
4、当然可以用非递归实现

二、归并排序说明

1、首先有一个f函数
void f(arr, L, R)
说明：在arr上，从L到R范围上让它变成有序的

2、递归调用

（1）先f(L, M)之间有序
（2）f(M+1, R)之间有序
（3）变成整体有序

左边是2、3、5，右边是0，5，6
准备一个一样长的辅助空间，然后左指针指向2，右指针指向0，谁小拷贝谁
然后右边的指针往后移，再次比较2和5，谁小拷贝谁，以此类推

（4）整体有序后，再把这一块空间刷回去

三、代码

package class03;public class Code01_MergeSort {/*** 变成整体有序* @param arr* @param L 数组下标* @param M 数组下标* @param R 数组下标*/public static void merge(int[] arr, int L, int M, int R) {int [] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}//要么p1越界了，要么p2越界了//看左边小于等于Mwhile (p1 <= M) {help[i++] = arr[p1++];}//还是右边小于等于Rwhile (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}}/*** 递归方法实现* arr[L...R]范围上，变成有序* @param arr*/public static void mergeSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L == R) { // base casereturn;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}/*** 非递归方法实现* @param arr*/public static void mergeSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;int mergeSize = 1;while (mergeSize < N) {int L = 0;while (L < N) {int M = L + mergeSize - 1;if (M >= N) {break;}int R = Math.min(M + mergeSize, N - 1);merge(arr, L, M, R);L = R + 1;}if (mergeSize > N / 2) { //防止溢出break;}mergeSize <<= 1; //左移后赋值，相当于乘2后赋值}}public static void main(String[] args) {int[] aaa = {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};int[] bbb = {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};mergeSort1(aaa);for (int i: aaa) {System.out.print(i + " ");}System.out.println();mergeSort2(bbb);for (int i: bbb) {System.out.print(i + " ");}System.out.println();}
}

（1）递归说明

（2）非递归说明

原理：
k=2
相邻两个数之间merge在一起
k=4
四个数一组，merge在一起
...
一直到k到达N或者超过N

回到代码，代码中mergeSize就是k，外层while循环
  N  10
  mergeSize  1
  L  0
  内层while循环
    M  0
    R  1
    merge(arr, 0, 0, 1)
    L  2
    
    M  2
    R  3
    merge(arr, 2, 2, 3)
    L  4
    
    M  4
    R  5
    merge(arr, 4, 4, 5)
    L  6
    
    ...

然后mergeSize变成2，变成4...

四、归并排序复杂度

T(N)=2*T(N/2)+O(N^1)
根据master可知时间复杂度为O(N*logN)
merge过程需要辅助数组，所以额外空间复杂度为O(N)
归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快