数据结构基础之《（9）

数据结构基础之《（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越界了
		//看左边小于等于M
		while (p1 <= M) {
			help[i++] = arr[p1++];
		}
		//还是右边小于等于R
		while (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 case
			return;
		}
		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

...