归并排序（Merge Sort）
- 基本思想
- 建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
- 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
- 自下而上的迭代
- 算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设置两个指针，初始位置为两个已经排序序列的起始位置
- 比较两个指针指向元素大小，选择较小的元素存放到新空间，并移动指针指向下一位置
- 重复，直到某一指针到达序列尾部
-
将另一序列剩下元素直接存入新序列尾部
例如：
mergeSort.jpg
-
动图演示
mergeSort.gif 代码实现
使用自上而下的递归法实现，分三个小方法，在代码中有详细注释，此处不多罗列
public static void mergeSort(int[] arr) {
if (null == arr || arr.length < 1) return;
sort(arr, 0, arr.length - 1);
}
/**
* 归并排序 主方法 - 递归实现
* @param arr 主数组
* @param start 排序起始索引
* @param end 排序终止索引
*/
public static void sort(int[] arr, int start, int end) {
if (start == end) return;
int mid = (start + end) / 2;
// 左区间递归
sort(arr, start, mid);
// 右区间递归
sort(arr, mid + 1, end);
// 合并
merge(arr, start, end, mid);
}
/**
* 数组合并
* @param arr
* @param left 左索引
* @param right 右索引
* @param mid 中间索引
*/
public static void merge(int[] arr, int left, int right, int mid) {
// [left, mid],[mid+1, right]
int[] temp = new int[right - left + 1];
// 定义数组遍历的左起始位置，和右起始位置
int ls = left, rs = mid + 1;
int tempIndex = 0;
while (ls <= mid && rs <= right) {
if (arr[ls] < arr[rs]) {
temp[tempIndex] = arr[ls];
ls++;
} else {
temp[tempIndex] = arr[rs];
rs++;
}
tempIndex++;
}
while (ls <= mid) {
temp[tempIndex] = arr[ls];
ls++;
tempIndex++;
}
while (rs <= right) {
temp[tempIndex] = arr[rs];
rs++;
tempIndex++;
}
// 将排序好的临时数组，写回原需排序数组
for (int i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
- 时间复杂度分析
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)
优化
可使用自下而上的迭代法实现，迭代的性能是会优于递归的，并且递归太深也存在内存溢出风险。
