forked from DreamCats/java-notes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
62 lines (56 loc) · 1.83 KB
/
MergeSort.java
File metadata and controls
62 lines (56 loc) · 1.83 KB
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
import java.util.Arrays;
/**
* @program JavaBooks
* @description: 归并排序
* @author: mf
* @create: 2019/08/13 19:38
*/
/*
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {10,34,5,3,4,2,1};
System.out.println(Arrays.toString(arr));
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int left, int right) {
if (left == right) return;
int mid = left + ((right - left) >> 1);
// left
mergeSort(arr, left, mid);
// right
mergeSort(arr, mid + 1, right);
// merge
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid) {
help[i++] = arr[p1++];
}
while(p2 <= right) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
}
}