归并排序

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
public class MSort {
public static void main(String[] args) {
MSort m = new MSort();
int[] r = {7,2,5,2,8,267,0};
m.mSort(r,0,r.length-1);
//MSort.sort(r,0,r.length-1);
for (int i : r) {
System.out.println(i);
}
}
void merge(int[] r, int low, int mid, int high){
int i = low;
int j = mid+1;
int k = low;

int[] t = new int[high+1];
while (i<=mid&&j<=high){
t[k++]=r[i]<=r[j]?r[i++]:r[j++];
}

while (i<=mid)
t[k++]=r[i++];
while (j<=high)
t[k++]=r[j++];
for (int l = low; l <= high; l++) {
r[l]=t[l];
}
}

void mSort(int[] r,int low, int high){
if (low==high)
return;
else {
int mid = (low+high)/2;
mSort(r,low,mid);
mSort(r,mid+1,high);
merge(r,low,mid,high);
}
}



private static void sort(int[] array, int start, int end) {
if (start >= end)
return;

int mid = (start + end) >> 1;
// 递归实现归并排序
sort(array, start, mid);
sort(array, mid + 1, end);
mergerSort(array, start, mid, end);
}

// 将两个有序序列归并为一个有序序列(二路归并)
private static void mergerSort(int[] array, int start, int mid, int end) {
// TODO Auto-generated method stub
int[] arr = new int[end + 1]; // 定义一个临时数组,用来存储排序后的结果
int low = start; // 临时数组的索引
int left = start;

int center = mid + 1;
// 取出最小值放入临时数组中
while (start <= mid && center <= end) {
arr[low++] = array[start] > array[center] ? array[center++] : array[start++];
}

// 若还有段序列不为空,则将其加入临时数组末尾

while (start <= mid) {
arr[low++] = array[start++];
}
while (center <= end) {
arr[low++] = array[center++];
}

// 将临时数组中的值copy到原数组中
for (int i = left; i <= end; i++) {
array[i] = arr[i];
}
}

}