归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

思路

分阶段可以理解为就是递归拆分子序列的过程。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤：

代码

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
package com.nanzx.sort;

import java.util.Arrays;

public class MergeSort {

	public static void main(String[] args) {
		int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 };
		mergeSort(arr, 0, arr.length-1);
		System.out.println("归并排序后=" + Arrays.toString(arr));
	}

	// 分+合方法
	public static void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2; // 中间索引
			// 向左递归进行分解
			mergeSort(arr, left, mid);
			// 向右递归进行分解
			mergeSort(arr, mid + 1, right);
			// 合并
			merge(arr, left, mid, right);

		}
	}

	public static void merge(int[] arr, int left, int mid, int right) {
		int i = left; // 初始化i, 左边有序序列的初始索引
		int j = mid + 1; // 初始化j, 右边有序序列的初始索引
		int[] temp = new int[right - left + 1];
		int t = 0; // 指向temp数组的当前索引

		// (一)
		// 先把左右两边(有序)的数据按照规则填充到temp数组
		// 直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}

		// (二)
		// 把有剩余数据的一边的数据依次全部填充到temp
		while (i <= mid) {
			temp[t++] = arr[i++];
		}
		while (j <= right) {
			temp[t++] = arr[j++];
		}

		// (三)
		// 将temp数组的元素拷贝到arr
		System.out.println("left: " + left + "  right:" + right + "  t:" + t);
		for (int k = 0; k < t; k++) {
			arr[left++] = temp[k];
		}
	}
}

运行结果

left: 0 right:1 t:2
left: 2 right:3 t:2
left: 0 right:3 t:4
left: 4 right:5 t:2
left: 6 right:7 t:2
left: 4 right:7 t:4
left: 0 right:7 t:8
归并排序后=[1, 2, 3, 4, 5, 6, 7, 8]

对于代码中mergeSort方法的理解

1
2
3
4
5
6
7
8
9
10
11
12
public static void mergeSort(int[] arr, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2; // 中间索引
		// 向左递归进行分解
		mergeSort(arr, left, mid);
		// 向右递归进行分解
		mergeSort(arr, mid + 1, right);
		// 合并
		merge(arr, left, mid, right);

	}
}

这个方法其实就是先一直分割左子列，分割到如图的第三列的 84 时，就不会再继续向左分割，不满足向左递归进行分解的条件，接着向右递归进行分解，发现条件也不满足，所以没有分割到如图的第四列（两条虚线紧夹着的位置），最后执行按序合并4和8的操作。回溯到8457，执行向右递归进行分解，分成57后也是不能在分解了，按序合并57。回溯到8457执行按序合并。

测试归并排序的速度

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
package com.nanzx.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class MergeSort {

	public static void main(String[] args) {
		// 创建要给8000000个的随机的数组 八百万
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);

		mergeSort(arr, 0, arr.length - 1);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是=" + date2Str);
	}

	// 分+合方法
	public static void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2; // 中间索引
			// 向左递归进行分解
			mergeSort(arr, left, mid);
			// 向右递归进行分解
			mergeSort(arr, mid + 1, right);
			// 合并
			merge(arr, left, mid, right);

		}
	}

	public static void merge(int[] arr, int left, int mid, int right) {
		int i = left; // 初始化i, 左边有序序列的初始索引
		int j = mid + 1; // 初始化j, 右边有序序列的初始索引
		int[] temp = new int[right - left + 1];
		int t = 0; // 指向temp数组的当前索引

		// (一)
		// 先把左右两边(有序)的数据按照规则填充到temp数组
		// 直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}

		// (二)
		// 把有剩余数据的一边的数据依次全部填充到temp
		while (i <= mid) {
			temp[t++] = arr[i++];
		}
		while (j <= right) {
			temp[t++] = arr[j++];
		}

		// (三)
		// 将temp数组的元素拷贝到arr
		for (int k = 0; k < t; k++) {
			arr[left++] = temp[k];
		}
	}
}

排序前的时间是=2020-08-03 15:07:12 排序后的时间是=2020-08-03 15:07:14