归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数开始，谁小就先取谁。然后再进行比较，如果有数列比较完了，那直接将另一个数列的数据依次取出即可。可以看出合并有序数列的效率是比较高的，可以达到O(n)。
1.2 算法基本思想
归并排序的核心思想其实很简单，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后分别对前后两部分进行排序，再将排好序的两部分数据合并在一起就可以了。归并排序使用的是分治思想，分治也即是分而治之，将一个大问题分解为小的子问题来解决。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。
1.3 归并排序复杂度分析
- 归并排序是一个稳定的排序算法，在进行子数组合并的时候，我们可以设置当元素大小相等时，先将前半部分的数据放入临时数组，这样就可以保证相等元素在排序后依然保持原来的顺序。
- 不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递归公式。
- 如果我们对n个元素进行归并排序所需要的时间是T(n)，那分解成两个子数组排序的时间都是
，而合并两个子数组的时间复杂度为 。所以，归并排序的时间复杂度计算公式为：O(n)
1.4 归并排序代码实现
package com.yuanxw.datastructure.chapter19;
import java.util.Arrays;
/**
* 归并排序
*/
public class MergeSort {
public static void main(String[] args) {
// int[] array = new int[]{10, -7, 8, -2, 5, -4};
// 定义需要排序的数组
int[] array = new int[]{
8, 4, 5, 7, 1, 3, 6, 2};
// 临时数组
int[] temp = new int[array.length];
System.out.println("【归并排序】前的结果：" + Arrays.toString(array));
// 拆分
mergeSort(array, 0, array.length - 1, temp);
System.out.println("【归并排序】后的结果：" + Arrays.toString(array));
}
/**
* 拆分数组
*
* @param array 原始数组
* @param left 数组左侧下标
* @param right 数组右侧下标
* @param temp 临时数组（中间数组）
*/
public static void mergeSort(int[] array, int left, int right, int[] temp) {
// 如果【left < right】成立，说明还没有拆分到最小单元
if (left < right) {
// 得到中间索引
int middle = (left + right) / 2;
// 递归-拆份左边的部分
mergeSort(array, left, middle, temp);
// 递归-拆份右边的部分
mergeSort(array, middle + 1, right, temp);
// 合并 数组
merge(array, left, middle, right, temp);
}
}
/**
* 合并数组
*
* @param array
* @param left
* @param middle
* @param right
* @param temp
*/
public static void merge(int[] array, int left, int middle, int right, int[] temp) {
// 左边最左侧下标
int leftIndex = left;
// 右边最左侧下标
int middleIndex = middle + 1;
// 临时数组
int tempIndex = 0;
while (leftIndex <= middle && middleIndex <= right) {
// 比较左右两边大小，分别放到temp临时数组中
if (array[leftIndex] <= array[middleIndex]) {
temp[tempIndex] = array[leftIndex];
tempIndex++;
leftIndex++;
} else {
temp[tempIndex] = array[middleIndex];
tempIndex++;
middleIndex++;
}
}
// 如果比较完毕, 第左边还有数剩下, 则全部填入temp
while (leftIndex <= middle) {
temp[tempIndex] = array[leftIndex];
tempIndex++;
leftIndex++;
}
// 如果比较完毕, 第右边还有数剩下, 则全部填入temp
while (middleIndex <= right) {
temp[tempIndex] = array[middleIndex];
tempIndex++;
middleIndex++;
}
// 将temp数组中的数据全部拷贝到array数组中
for (int i = 0; i < tempIndex; i++) {
array[left + i] = temp[i];
}
}
}
执行结果：
【归并排序】前的结果：[8, 4, 5, 7, 1, 3, 6, 2]
【归并排序】后的结果：[1, 2, 3, 4, 5, 6, 7, 8]