【算法】归并排序

原理说明：

1. 将程序中待排序数字分为若干组，每个数字分为一组
2. 将若干个组件两两合并，保证合并后的组是有序的
3. 重复第二步操作直到只剩下一组，排序完成

思想示意图：

代码实现：

public class MergetSort {
	
	public static void main(String[] args) {
		int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
		int temp[] = new int[arr.length]; // 归并排序需要一个额外空间
		mergeSort(arr, 0, arr.length - 1, temp);

		System.out.println("归并排序后=" + Arrays.)
	}
	
	// 分 + 合方法
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left < right) {
			int mid = (left + right) / 2; // 中间索引
			// 向左递归进行分解
			mergeSort(arr, left, mid, temp);
			// 向右递归进行分解
			mergeSort(arr, mid + 1， right, temp);
			// 合并
			merge(arr, left, mid, right, temp);
		}
	}

	// 合并的方法
	/**
	*
	* @param arr 排序的原始数组
	* @param left 左边有序序列的初始索引
	* @param mid 中间索引
	* @param right 右边索引
	* @param temp 做中转的数组
	*/
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		int i = left; // 初始化i，左边有序序列的初始索引
		int j = mid + 1; // 初始化j，右边有序序列的初始索引
		int t = 0; // 指向temp数组的当前索引
		
		//（一）
		// 先把左右两边（有序）的数据按照规则填充到temp数组
		// 直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) { // 继续
			// 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
			// 即将左边的当前元素，填充到temp数组
			// 然后 t++，i++
			if (arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else { // 反之，将右边有序序列的当前元素，填充到temp数组
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}

		// (二)
		// 把有剩余数据的一边的数据依次全部填充到temp
		while (i <= mid) { // 左边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[i];
			t += 1;
			i += 1;
		}
		
		while (j <= mid) { // 右边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}

		// (三)
		// 将temp数组的元素拷贝到arr
		// 注意，并不是每次都拷贝所有
		t = 0;
		int tempLeft = left; // 
		// 第一次合并 tempLeft = 0, right = 1 // tempLeft = 2 right = 3 // tL = 0 ri = 3
		// 最后一次tempLeft = 0 right = 7
		System.out.println("tempLeft = " + tempLeft + " right =" + right);
		while (tempLeft <= right) { 
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;
		}

	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

运行结果：