思路
有数组[2, 1, -3, -15, 25, 16, 0, 8]如下：
image.png
现对该数组进行排序，使用归并排序算法。
先来讲解一下归并排序的思路，大概分为如下几个步骤：
- 先将原数组先进行拆分，拆分成若干个足够小的子数组；
- 将子数组进行排序；
- 将子数组一一进行归并，直到所有子数组被归并。
讲解
OK，思路了解了，下面就用图示来演示一下各个步骤是怎么做的。
1. 先将原数组先进行拆分，拆分成若干个足够小的子数组：
我们先把上面的数组进行第一次拆分：
image.png
拆分成了两部分，分别为[2, 1, -3, -15]和[25, 16, 0, 8]
这样的拆分不够小，我们继续进行拆分：
image.png
这样就又把两个子数组分别拆分成了更小的两个子数组[2, 1]、[-3, -15]、[25, 16]、[0, 8]。
好了，这样的拆分足够小了，进行下一步。
2. 将子数组进行排序：
排序后的四个子数组为：
image.png
子数组排序后，就该进行最后一步了。
3. 将子数组一一进行归并，直到所有子数组被归并：
先将第一个子数组和第二个子数组进行归并，归并的步骤其实也很简单，就是将两个子数组的元素从左到右依次进行比较，按顺序进行存放即可。
这时候需要创建一个空数组，对结果集进行一个存放。首先对比1和-15，1比-15要大，所以先把-15放到结果数组中：
image.png
然后对比1和-3,1依然是大于-3，所以把-3放到结果数组中：
image.png
这时候第二个子数组已经被搬空了，那么直接把第一个子数组的数据依次放入结果数组即可：
image.png
这样前面两个子数组就完成了归并操作。那么后面两个子数组也是同样的归并方式，归并结果如下：
image.png
这样就归并成了两个子数组，然后再对这两个子数组进行进一步的归并操作，操作依然跟上面是一样的，一个一个对比，最终就归并成了如下结果：
image.png
这样就完成了一个简单的归并排序。
但一般生产中可能需要排序的数据会比较大，那么拆分的时候可能拆分到15个左右元素的时候，就不再进行拆分了，而是使用插入排序的方式对子数组进行排序，然后再对排好序的子数组进行归并。
实现
下面来用代码实现一下归并排序：
@Test
public void sortTest() {
int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8};
int[] sortedArray = mergeSort(nums);
System.out.println(Arrays.toString(sortedArray));
}
private int[] mergeSort(int[] nums) {
// 数组大小小于2，直接返回
if (nums.length < 2) {
return nums;
}
// 数组大小等于2，排序并返回
if (nums.length == 2) {
if (nums[0] > nums[1]) {
swap(nums, 0, 1);
}
return nums;
}
// 数组拆分
int[] left = Arrays.copyOfRange(nums, 0, nums.length / 2);
int[] right = Arrays.copyOfRange(nums, nums.length / 2, nums.length);
// 递归归并
return merge(mergeSort(left), mergeSort(right));
}
private int[] merge(int[] left, int[] right) {
// 声明结果数组
int[] result = new int[left.length + right.length];
// 开始遍历，每次放入结果数组一个元素
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
// 如果左子数组已经归并完，直接放入右子数组
if (i >= left.length) {
result[index] = right[j++];
// 如果右子数组已经归并完，直接放入左子数组
} else if (j >= right.length) {
result[index] = left[i++];
// 如果两个子数组都没有归并完，比较大小并放入结果数组
} else if (left[i] < right[j]) {
result[index] = left[i++];
}else{
result[index] = right[j++];
}
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
这样就实现了一个简单的归并排序，看下执行结果：
image.png
其实这叫二路归并，另外还有多路归并，其实知道原理了，也不难实现，比如三路归并：
@Test
public void sortTest() {
int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8};
int[] sortedArray = mergeSort(nums);
System.out.println(Arrays.toString(sortedArray));
}
private int[] mergeSort(int[] nums) {
// 数组大小小于2，直接返回
if (nums.length < 2) {
return nums;
}
// 数组大小等于2，排序并返回
if (nums.length == 2) {
if (nums[0] > nums[1]) {
swap(nums, 0, 1);
}
return nums;
}
// 数组拆分
int[] left = Arrays.copyOfRange(nums, 0, nums.length / 3);
int[] mid = Arrays.copyOfRange(nums, nums.length / 3, nums.length / 3 * 2);
int[] right = Arrays.copyOfRange(nums, nums.length / 3 * 2, nums.length);
// 递归归并
return merge(mergeSort(left), mergeSort(mid), mergeSort(right));
}
private int[] merge(int[] left, int[] mid, int[] right) {
// 声明结果数组
int[] result = new int[left.length + mid.length + right.length];
// 开始遍历，每次放入结果数组一个元素
for (int index = 0, i = 0, j = 0, k = 0; index < result.length; index++) {
if (i >= left.length) {
if (j >= mid.length) {
result[index] = right[k++];
} else {
if (mid[j] < right[k]) {
result[index] = mid[j++];
} else {
result[index] = right[k++];
}
}
} else if (j >= mid.length) {
if (k >= right.length) {
result[index] = left[i++];
} else {
if (left[i] < right[k]) {
result[index] = left[i++];
} else {
result[index] = right[k++];
}
}
} else if (k >= right.length) {
if (left[i] < mid[j]) {
result[index] = left[i++];
} else {
result[index] = mid[j++];
}
} else {
if (left[i] < mid[j]) {
if (left[i] < right[k]) {
result[index] = left[i++];
} else {
result[index] = right[k++];
}
} else if (left[i] >= mid[j]) {
if (mid[j] < right[k]) {
result[index] = mid[j++];
} else {
result[index] = right[k++];
}
}
}
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
道理是一样的，执行结果也是一样的：
image.png
好的，归并排序就说这么多。有不对不完善的地方欢迎指正。
