-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
70 lines (66 loc) · 1.98 KB
/
MergeSort.java
File metadata and controls
70 lines (66 loc) · 1.98 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
63
64
65
66
67
68
69
70
package com.ywh.sorting;
/**
* 归并排序
* [排序] [稳定排序] [分治]
*
* @author ywh
* @since 14/11/2019
*/
public class MergeSort {
private void mergeSort(int[] arr, int low, int high, int[] tmp) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(arr, low, mid, tmp);
mergeSort(arr, mid + 1, high, tmp);
// System.arraycopy(arr, low, tmp, low, high - low + 1);
for (int i = low; i <= high; tmp[i] = arr[i++]);
for (int l = low, r = mid + 1, k = low; k <= high; k++) {
if (l > mid) {
arr[k] = tmp[r++];
} else if (r > high) {
arr[k] = tmp[l++];
} else if (tmp[l] < tmp[r]) {
arr[k] = tmp[l++];
} else {
arr[k] = tmp[r++];
}
}
}
/**
* 递归解法（自顶向下）
*
* @param arr
*/
public void sortRecursive(int[] arr) {
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
/**
* 迭代解法（自底向上）
*
* @param arr
*/
public void sortIterative(int[] arr) {
int n = arr.length;
int[] tmp = new int[n];
for (int len = 1; len < n; len *= 2) {
for (int low = 0; low < n; low += 2 * len) {
int mid = Math.min(low + len - 1, n - 1), high = Math.min(low + 2 * len - 1, n - 1);
System.arraycopy(arr, low, tmp, low, high - low + 1);
int i = low, j = mid + 1;
for (int k = low; k <= high; k++) {
if (i > mid) {
arr[k] = tmp[j++];
} else if (j > high) {
arr[k] = tmp[i++];
} else if (tmp[i] < tmp[j]) {
arr[k] = tmp[i++];
} else {
arr[k] = tmp[j++];
}
}
}
}
}
}