归并排序
|字数总计:1.2k|阅读时长:5分钟|阅读量:|
归并排序
基本思想
归并排序（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;
int j = mid + 1;
int[] temp = new int[right - left + 1];
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
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) {
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 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;
int j = mid + 1;
int[] temp = new int[right - left + 1];
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
for (int k = 0; k < t; k++) {
arr[left++] = temp[k];
}
}
}
|
排序前的时间是=2020-08-03 15:07:12 排序后的时间是=2020-08-03 15:07:14
微信
支付宝