小朋友学数据结构（4）：归并排序
在学习归并排序之前，请大体浏览一下 程序员必须掌握的8大排序算法
（一）基本思想
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
7-1.jpg
（二）代码实现
import java.util.Arrays;
public class Sort {
public static void mergeSort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] data, int left, int right) {
if (left < right) {
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
}
}
private static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int centerNext = center + 1;
// 记录临时数组的索引
int tmp = left;
int index = left;
while (left <= center && centerNext <= right) {
//从两个数组中取出最小的放入临时数组
if (data[left] <= data[centerNext]) {
tmpArr[tmp++] = data[left++];
} else {
tmpArr[tmp++] = data[centerNext++];
}
}
// 若右边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (centerNext <= right) {
tmpArr[tmp++] = data[centerNext++];
}
// 若左边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (left <= center) {
tmpArr[tmp++] = data[left++];
}
// 将临时数组中的内容复制回原数组
while (index <= right) {
data[index] = tmpArr[index++];
}
}
public static void main(String[] args) {
int[] arr = {57, 68, 59, 52, 72, 28, 96, 33};
System.out.println("Original array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
运行结果：
> javac -encoding utf-8 Sort.java
> java Sort
Original array: [57, 68, 59, 52, 72, 28, 96, 33]
Sorted array: [28, 33, 52, 57, 59, 68, 72, 96]
（三）程序分析
咱们用数组data[8] = [57, 68, 59, 52, 72, 28, 96, 33]来分析一下上面程序的执行过程。
1 sort方法的具体执行情况
调用mergeSort()方法会调用sort(data, 0, 7)。
sort()内部用了递归，第一次被调用时包含了3步：
sort(data, 0, 3)
sort(data, 4, 7)
merge(data, 0, 3, 7)
将递归展开，可进一步细分为7步：
sort(data, 0, 1)
sort(data, 2, 3)
merge(data, 0, 1, 3)
sort(data, 4, 5)
sort(data, 6, 7)
merge(data, 4, 5, 7)
merge(data, 0, 3, 7)
再次将递归展开，进一步细分为15步
sort(data, 0, 0)
sort(data, 1, 1)
merge(data, 0, 0, 1)
sort(data, 2, 2)
sort(data, 3, 3)
merge(data, 2, 2, 3)
merge(data, 0, 1, 3)
sort(data, 4, 4)
sort(data, 5, 5)
merge(data, 4, 4, 5)
sort(data, 6, 6)
sort(data, 7, 7)
merge(data, 6, 6, 7)
merge(data, 4, 5, 7)
merge(data, 0, 3, 7)
sort里面只有在left<right时才会执行，所以上面的8个sort都不执行。
相当于上面的15步只剩下7步：
merge(data, 0, 0, 1)
merge(data, 2, 2, 3)
merge(data, 0, 1, 3)
merge(data, 4, 4, 5)
merge(data, 6, 6, 7)
merge(data, 4, 5, 7)
merge(data, 0, 3, 7)
2 merge方法的具体执行情况
(1) merge(data, 0, 0, 1)
tmpArr[] = new int[8], centerNext = 1, tmp = 0, index = 0
第一个while循环：
0<=0 && 1<=1 成立
data[left]=data[0]=57
data[centerNext]=data[1]=68
if条件成立，执行tmpArr[0]=data[0]=57
tmp自加变成1，left自加变成1，
此时while条件left <= center不再成立，循环结束。
第二个while循环：
centerNext=1，right= 1, centerNext<=right成立
tmpArr[tmp]=tmpArr[1]=data[1]=68
tmp自加变成2，centerNext自加变成2，
此时while条件centerNext<=right不再成立，循环结束。
第三个while循环：
left=1, center=0，left <= center不成立，循环不执行。
第四个while循环：
把tmpArr中的数据逐个赋值给data
data[0] = tmpArr[0] = 57，index自加变为1
data[1] = tmpArr[1] = 68，index自加变为2，循环结束
这样，就达到了data[0]与data[1]排序的目的，这里因为data[0]和data[1]本来就是有序的，看不出效果。下一个merge立马就能看出效果。
(2) merge(data, 2, 2, 3)
tmpArr[] = new int[8], centerNext = 3, tmp = 2, index = 2
第一个while循环：
2<=2 && 3<=3 成立
data[left] = data[2] = 59
data[centerNext] = data[3] = 52
if条件不成立，执行else语句
tmpArr[2] = data[3] = 52
tmp自加变成3，centerNext自加变成4
此时while条件centerNext <= right不再成立，循环结束
第二个while循环：
centerNext = 4，right= 3, centerNext <= right 不成立，循环结束
第三个while循环：
left = 2, center = 2，left <= center成立，tmpArr[3] = data[2] = 59
tmp自加变为4，left自加变为3，此时left <= center不成立，循环结束
第四个while循环：
作用是把tmpArr中的数据逐个赋值给data
index = 2, right = 3, index <= right成立
data[index] = data[2] = tmpArr[index] = tmpArr[2] = 52
index自加变为3，此时index <= right仍然成立
data[index] = data[3] = tmpArr[index] = tmpArr[3] = 59
index自加变为4，此时index <= right不成立，循环结束。
注意，现在data变为[57,68, 52, 59, 72, 28, 96, 33]
可以观察到，data[0]和data[1]是按顺序排列的，data[2]和data[3]也是按顺序排列的（原先这俩是反序排列）。
（3）merge(data, 0, 1, 3)
这一步的作用，是把data里的元素从第0个到第3个（共4个元素），进行归并排序。
第一个while循环：
tmpArr[] = new int[8], left = 0, center = 1, centerNext = 2, right = 3, tmp = 0, index = 0
循环条件left <= center && centerNext <= right成立，进入循环
if条件data[0] = 57, data[2] = 52, data[0] <= data[2]不成立，
执行else语句tmpArr[0] = data[2] = 52
tmp自加变成1，centerNext 自加变成3
循环条件left <= center && centerNext <= right仍然成立，再次进入循环
if语句中data[left] = data[0] = 57, data[centerNext] = data[3] = 59，57 <= 59成立，
执行if语句tmpArr[1] = data[0] = 57，tmp自加变成2，left自加变成1
循环条件 left <= center && centerNext <= right第三次成立，第三次进入循环
if语句中，data[left] = data[1] = 68, data[centerNext] = data[3] = 59, 68 < 59不成立
执行else语句tmpArr[2] = data[3] = 59, tmp自加变为3，centerNext自加变成4
此时循环条件left <= center && centerNext <= right不成立，循环结束
第二个while循环：
centerNext = 4, right = 3, 4 <= 3不成立，循环不执行。
第三个while循环：
left = 1, center = 1, 1 <= 1，循环条件成立
tmpArr[3] = data[1] = 68,
tmp自加后变为4，left自加后变为2，此时循环条件不成立，循环结束
第四个while循环
index = 0, right = 3, data[0] = tmpArr[0] = 52
index自加变为1，data[1] = tmpArr[1] = 57
index自加变为2，data[2] = tmpArr[2] = 59
index自加变为3，data[3] = tmpArr[3] = 68
index自加变为4，index <= right不成立，循环结束
至此，data[] = {52, 57, 59, 68, 72, 28, 96, 33}
（4）merge(data, 4, 4, 5)
这一步是在前三次的mege结果的基础上，对第4个和第5个元素进行排序，结果为
data[] = {52, 57, 59, 68, 28, 72, 96, 33}
（5）merge(data, 6, 6, 7)
这一步是在前四次的mege结果的基础上，对第6个和第7个元素进行排序，结果为
data[] = {52, 57, 59, 68, 28, 72, 33, 96}
（6）merge(data, 4, 5, 7)
这一步是在前五次的mege结果的基础上，对第4个至第7个元素进行排序，结果为
data[] = {52, 57, 59, 68, 28, 33, 72, 96}
（7）merge(data, 0, 3, 7)
这一步是在前五次的mege结果的基础上，对第4个至第7个元素进行排序，结果为
data[] = {28, 33, 52, 57, 59, 68, 72, 96}
至此，data数组的8个元素已排序完毕。
TopCoder & Codeforces & AtCoder交流QQ群：648202993
更多内容请关注微信公众号
wechat_public_header.jpg
