|
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 |
public class MergeSort { private
static void mergeSortTest() { int[] in = { 2, 5, 3, 8, 6, 7, 1, 4, 0, 9
}; Utils.printArray("归并排序前：",in); int
a[] = mergeSort(in); Utils.printArray("归并排序后：",a); } private
static int[] mergeSort(int[] arr) { if
(arr.length == 1) { return
arr; } else
{ int[] arrL = new
int[arr.length / 2]; int[] arrR = new
int[arr.length - arr.length / 2]; int
mid = arr.length / 2; for
(int i = 0; i < mid; i++) { arrL[i] = arr[i]; } for
(int i = mid, j = 0; i < arr.length; i++, j++) { arrR[j] = arr[i]; } int[] sortedArrL = mergeSort(arrL); int[] sortedArrR = mergeSort(arrR); int[] resultArr = mergeTwoArr(sortedArrL, sortedArrR); return
resultArr; } } private
static int[] mergeTwoArr(int[] arrL, int[] arrR) { int
i = 0, j = 0; int[] arrTmp = new
int[arrL.length + arrR.length]; int
foot = 0; while
(i < arrL.length && j < arrR.length) { if
(arrL[i] <= arrR[j]) { arrTmp[foot++] = arrL[i++]; } else
{ arrTmp[foot++] = arrR[j++]; } } if
(i == arrL.length) { while
(j < arrR.length) { arrTmp[foot++] = arrR[j++]; } } else
{ while
(i < arrL.length) { arrTmp[foot++] = arrL[i++]; } } return
arrTmp; } public
static void main(String[] args) { mergeSortTest(); }} |
原文：http://www.cnblogs.com/zhaofeng555/p/3594875.html