java 归并排序 2017年7月12日
未分类
0 条评论

java 归并排序

最近看了个讲解归并排序的视频，是用C语言实现的。我想用java再实现一遍，加深印象，相当于做个笔记。

感觉这个系列的视频做得很好，讲得非常详细，有机会我会逐一实现视频中的代码。

参考：http://www.bilibili.com/video/av9982752/

 

一、实现过程

（1）使用分治的思想，把大的数组拆分成两个较小的数组

MergeSort.java

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
package com.test.Sort;
 
public class MergeSort {
 
public static void merge(int[] arr, int l, int m, int r) {
 
int left_size = m - l;
 
int right_size = r - m + 1;
 
int[] left = new int[left_size];
int[] right = new int[right_size];
 
for (int i = l; i < m; i++) {
 
left[i - l] = arr[i];
}
 
for (int i = m; i <= r; i++) {
 
right[i - m] = arr[i];
}
 
for (int i = 0; i < left.length; i++) {
 
System.out.print(left[i] + " ");
}
 
System.out.println();
 
for (int i = 0; i < right.length; i++) {
 
System.out.print(right[i] + " ");
}
}
 
public static void main(String[] args) {
 
int[] arr = new int[] { 2, 8, 9, 10, 4, 5, 6, 7 };
 
int l = 0;
int r = 7;
int m = 4;
 
merge(arr, l, m, r);
}
}

运行结果为：

1
2
2 8 9 10
4 5 6 7

至此，可以根据l、m、r调整两个较小的数组。

通过两个较小的数组的相互比较，可以得到排序结果。

（2）两个数组中的元素相互比较，进行初步排序

MergeSort.java

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
package com.test.Sort;
 
public class MergeSort {
 
public static void merge(int[] arr, int l, int m, int r) {
 
int left_size = m - l;
 
int right_size = r - m + 1;
 
int[] left = new int[left_size];
int[] right = new int[right_size];
 
for (int i = l; i < m; i++) {
 
left[i - l] = arr[i];
}
 
for (int i = m; i <= r; i++) {
 
right[i - m] = arr[i];
}
 
int i = 0, j = 0, k = l;
 
while (i < left_size && j < right_size) {
 
if (left[i] <= right[j]) {
 
arr[k] = left[i];
 
i++;
k++;
 
} else {
 
arr[k] = right[j];
 
j++;
k++;
}
}
 
while (i < left_size) {
 
arr[k] = left[i];
 
i++;
k++;
}
 
while (j < right_size) {
 
arr[k] = right[j];
 
j++;
k++;
}
}
 
public static void main(String[] args) {
 
int[] arr = new int[] { 2, 8, 9, 10, 4, 5, 6, 7 };
 
int l = 0;
int r = 7;
int m = 4;
 
merge(arr, l, m, r);
 
for (int i : arr) {
 
System.out.print(i + " ");
}
}
}

运行结果为：

1
2 4 5 6 7 8 9 10

可喜可贺，归并排序已经搞定了!

有人会说：“你这完全就是诈和啊！你给的数组{ 2, 8, 9, 10, 4, 5, 6, 7 }是特殊情况，分成两个较小数组时，刚好就是有序的！”

没错，如果把数组改成乱序的，比如{ 5, 4, 8, 7, 9, 6, 2, 10 }，结果就变成了：

1
5 4 8 7 9 6 2 10

这说明程序依然是不完整的。那么接下来怎么办？

（3）使用递归，改进排序

我的思路是这样的：

首先要知道，我们无法保证某个数组中的元素是有序的。所以我们把数组拆开，得到更小的数组，做归并排序。

拆开后的数组还是不能保证有序，那么我们就继续拆开，得到更小的数组，再做归并排序。

如果把原始数组不断的拆开，不断地做归并排序，最后可以得到很多非常小的数组。

当然，拆分是有极限的。拆分到最后，如果数组中只有一个元素，当然无法继续拆分下去，在此同时，我们也能保证此处的元素是有序的（容量为2的数组拆分成两个容量为1的小数组，两个数组中唯一的元素进行大小比较，结果绝对是有序的）。

所以，我们要做的就是写个递归，不断地拆分数组，做归并排序，直到所有元素都有序为止。

那么问题来了，既然要递归，我们什么时候停下来？

当一个数组不能再拆分了，就可以停下来了（只有一个元素，无法做拆分比较）。

MergeSort.java

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
87
88
89
90
91
package com.test.Sort;
 
public class MergeSort {
 
public static void merge(int[] arr, int l, int m, int r) {
 
int left_size = m - l;
 
int right_size = r - m + 1;
 
int[] left = new int[left_size];
int[] right = new int[right_size];
 
for (int i = l; i < m; i++) {
 
left[i - l] = arr[i];
}
 
for (int i = m; i <= r; i++) {
 
right[i - m] = arr[i];
}
 
int i = 0, j = 0, k = l;
 
while (i < left_size && j < right_size) {
 
if (left[i] <= right[j]) {
 
arr[k] = left[i];
 
i++;
k++;
 
} else {
 
arr[k] = right[j];
 
j++;
k++;
}
}
 
while (i < left_size) {
 
arr[k] = left[i];
 
i++;
k++;
}
 
while (j < right_size) {
 
arr[k] = right[j];
 
j++;
k++;
}
}
 
public static void mergeSort(int[] arr, int l, int r) {
 
if (l == r) { // 当l = r，数组无法再细分下去了，已经是有序的，直接退出
 
return;
 
} else {
 
int m = (l + r) / 2;
 
mergeSort(arr, l, m); // 左半边递归
mergeSort(arr, m + 1, r); // 右半边递归
merge(arr, l, m + 1, r); // 做一次归并排序
}
}
 
public static void main(String[] args) {
 
int[] arr = new int[] { 5, 4, 8, 7, 9, 6, 2, 10 };
 
int l = 0;
int r = 7;
 
mergeSort(arr, l, r);
 
for (int i : arr) {
 
System.out.print(i + " ");
}
}
}

结果为：

1
2 4 5 6 7 8 9 10

数次递归后，可以保证数据是有序的。

二、总结

从宏观上看不一定好理解，所以我推荐去看视频，讲得很清楚。

Post Views: 154