hunkier

学习笔记,开源代码,技术分享

归并排序

归并 (Merge) 排序法是将两个 (或两个以上)有序表合并成一个新的有序表,即把待排序序列分为多干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

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 MergeSortTest {
public static void main(String[] args){
int[] data = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7};
print(data);
mergeSort(data);
System.out.println("排序后的数组");
print(data);
}

public static void mergeSort(int[] data){
sort(data,0,data.length-1);
}

public void sort(int[] data, int left, int right){
if(left>=right){
return;
}
// 找出中间索引
int center = (left + right)/2;
// 对左边数组进行递归
sort(data,left,center);
// 对右边数组进行递归
sort(data, center+1, right);
// 合并
merge(data, left, center, right);
print(data);
}

/**
* 将两个数组进行归并,归并前面 2 个数组已经有序,归并后依然有序
*
* @param data
* 数组对象
* @param left
* 左数组的第一个元素的索引
* @param center
* 左数组的最后一个元素的索引,center+1 是右数组第一个元素的索引
* @param right
* 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 临时数组
int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int third = left;
// 缓存数组第一个元素的索引
int tmp = left;
while(left <= center && mid <= right){
// 从两个数组中取出最小的放入临时数组
if(data[left] <= data[mid]){
tmpArr[third++] = data[left++];
}else {
tempArr[third++] = data[mid++];
}
}

// 剩余部分依次放入临时数组 (实际上两个 while 只会执行其中一个)
while(mid <=right){
tmpArr[third++] = data[mid++];
}
while(left <= center){
temArr[third++] = data[left++];
}

// 将临时数组中的内容拷贝会原数组中
// (原 left-right 范围的内容被复制回原数组)
while(tmp <= right){
data[tmp] = tempArr[tmp++];
}
}

public static void print(int[] data){
for(int i = 0 ; i < data.length; i++){
System.out.print(data[i] + "\t");
}
System.out.println();
}


}
谢谢你请我喝牛奶

欢迎关注我的其它发布渠道