Java 使用合并排序对数组排序。
使用合并排序对数组排序。
实例源码：
源代码：
执行
执行中...
x
1
2
import java.security.SecureRandom;3
4
import java.util.Arrays;5
6
/**7
时 代 J a v a 公 众 号 - N o w J a v a . c o m8
**/9
10
public class Main11
12
{13
14
// calls recursive split method to begin merge sorting15
16
public static void mergeSort(int[] data)17
18
{19
20
sortArray(data, 0, data.length - 1); // sort entire array21
22
} 23
24
25
// splits array, sorts subarrays and merges subarrays into sorted array26
27
private static void sortArray(int[] data, int low, int high) /** from 时代Java公众号 - nowjava.com**/28
29
{30
31
// test base case; size of array equals 1 32
33
if ((high - low) >= 1) // if not base case34
35
{36
37
int middle1 = (low + high) / 2; // calculate middle of array38
39
int middle2 = middle1 + 1; // calculate next element over 40
41
42
// output split step43
44
System.out.printf("split: %s%n", subarrayString(data, low, high));45
46
System.out.printf(" %s%n", subarrayString(data, low, middle1));47
48
System.out.printf(" %s%n%n",subarrayString(data, middle2, high));49
50
51
// split array in half; sort each half (recursive calls)52
53
sortArray(data, low, middle1); // first half of array 54
55
sortArray(data, middle2, high); // second half of array 56
57
58
// merge two sorted arrays after split calls return59
60
merge (data, low, middle1, middle2, high); 61
62
} 63
64
} 65
66
67
68
// merge two sorted subarrays into one sorted subarray 69
70
private static void merge(int[] data, int left, int middle1, int middle2, int right){71
72
int leftIndex = left; // index into left subarray 73
74
int rightIndex = middle2; // index into right subarray 75
76
int combinedIndex = left; // index into temporary working array77
78
int[] combined = new int[data.length]; // working array 79
80
81
82
// output two subarrays before merging83
84
System.out.printf("merge: %s%n", subarrayString(data, left, middle1));85
86
System.out.printf(" %s%n", subarrayString(data, middle2, right));87
88
89
// merge arrays until reaching end of either 90
91
while (leftIndex <= middle1 && rightIndex <= right)92
93
{94
95
// place smaller of two current elements into result 96
97
// and move to next space in arrays 98
99
if (data[leftIndex] <= data[rightIndex]) 100
101
combined[combinedIndex++] = data[leftIndex++]; 102
103
else 104
105
combined[combinedIndex++] = data[rightIndex++];106
107
} 108
109
110
111
// if left array is empty 112
113
if (leftIndex == middle2) 114
115
// copy in rest of right array 116
117
while (rightIndex <= right) 118
119
combined[combinedIndex++] = data[rightIndex++];120
121
else // right array is empty 122
123
// copy in rest of left array 124
125
while (leftIndex <= middle1) 126
127
combined[combinedIndex++] = data[leftIndex++]; 128
129
130
// copy values back into original array131
132
for (int i = left; i <= right; i++) 133
134
data[i] = combined[i]; 135
136
137
// output merged array138
139
System.out.printf(" %s%n%n", 140
141
subarrayString(data, left, right));142
143
} 144
145
146
// method to output certain values in array147
148
private static String subarrayString(int[] data, int low, int high)149
150
{151
152
StringBuilder temporary = new StringBuilder();153
154
// output spaces for alignment155
156
for (int i = 0; i < low; i++)157
158
temporary.append(" ");159
160
161
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java