算法图解
典型的分治法, 分是把排序问题分解到最小单位(即: 1个数排序), 治把子树的排序结果向上合成上一层级父亲的排序结果, 下图描述的是治的过程
- 先递归对序列进行
分解成最小单元 - 逐级计算
治的结果
实现
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
private static void doSort(int[] arr, int[] tmp, int start, int end) {
if (start < end) {
int mid = (end + start) / 2;
doSort(arr, tmp, start, mid);
doSort(arr, tmp, mid + 1, end);
merge(arr, tmp, start, mid, end);
}
}
private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
int i = start;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
tmp[t++] = arr[i++];
}
if (arr[i] > arr[j]) {
tmp[t++] = arr[j++];
}
}
while (i <= mid) {
tmp[t++] = arr[i++];
}
while (j <= end) {
tmp[t++] = arr[j++];
}
System.arraycopy(tmp, 0, arr, start, end - start + 1);
}
时间复杂度
O(nlogn)
数组被分成了二叉树,二叉树的层高 log2n , 每层需要比对的次数 n
f(n) = n * log2n = O(nlogn)
空间复杂度
O(n)
用了一个temp数组,来缓存中间处理的数据, 当数据量很大的时候需要考虑这里的空间浪费问题
完整代码
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
class MergeSort {
private static void sort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int[] tmp = new int[array.length];
int length = array.length;
doSort(array, tmp, 0, length - 1);
}
private static void doSort(int[] arr, int[] tmp, int start, int end) {
if (start < end) {
int mid = (end + start) / 2;
doSort(arr, tmp, start, mid);
doSort(arr, tmp, mid + 1, end);
merge(arr, tmp, start, mid, end);
}
}
private static void merge(int[] arr, int[] tmp, int start, int mid, int end){
int i = start;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
tmp[t++] = arr[i++];
}
if (arr[i] > arr[j]) {
tmp[t++] = arr[j++];
}
}
while (i <= mid) {
tmp[t++] = arr[i++];
}
while (j <= end) {
tmp[t++] = arr[j++];
}
System.arraycopy(tmp, 0, arr, start, end - start + 1);
}
public static void main(String[] args) {
int[] array = {111, 52, 77, 98, 36, 12, 12, 48};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t : array) {
builder.append(t + " ");
}
return builder.toString();
}
}
参考
https://www.cnblogs.com/chengxiao/p/6194356.html
