七大排序之归并排序
前言
博主个人社区： 开发与算法学习社区博主个人主页：Killing Vibe的博客
欢迎大家加入，一起交流学习~~
一、算法思路
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
动图如下：
其实就是分为归和并两个过程：
归： 不断将原数组拆分为子数组（一分为二），直到每个子数组只剩下一个元素 = 》 归过程结束
并：不断合并相邻的两个子数组为一个大的子数组，合并的过程就是将两个已经有序的子数组合并为一
举个栗子：
如下图所示的待排序序列，经过不断的归过程变成了一个个的小数组：
当每个子数组都只剩下一个元素时，每个子数组都是一个有序数组，然后开始两两合并。
如下是并过程：
时间复杂度：稳定O（nlogn） 空间复杂度：O（n）
二、代码实现
代码如下：
private static void mergeSortInternal(int[] arr, int l, int r) {
// 2.小数组直接使用插入排序
if (r - l <= 15) {
insertionSort(arr,l,r);
return;
}
// int mid = (l + r) / 2;
// l = 2,r = 4 mid = 3 = 2 + (4 - 2) / 2 = 3
int mid = l + ((r - l) / 2);
mergeSortInternal(arr,l,mid);
mergeSortInternal(arr,mid + 1,r);
// arr[l..mid] 和 arr[mid + 1...r]有序 只需要合并这两个子数组即可
// 1.到底什么时候才需要合并 arr[mid] < arr[mid + 1] 说明？arr[mid] 数组1的最大值 arr[mid + 1]数组2的最小值
// 整个数组已经有序了，那你还合并个der
if (arr[mid] > arr[mid + 1]) {
// 前后两个子数组还存在乱序，才需要合并
merge(arr,l,mid,r);
}
}
/**
* 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
* @param arr
* @param l
* @param mid
* @param r
*/
private static void merge(int[] arr, int l, int mid, int r) {
// 先创建一个新的数组aux,将子数组的值复制给新数组
int[] aux = new int[r - l + 1];
// l = 2,r = 4
// arr[2..4]
// aux[0..2] 索引下标差了个l偏移量
for (int i = 0; i < aux.length; i++) {
// aux的索引下标0...arr.length - 1
// arr的下标l...r
aux[i] = arr[i + l];
}
// 数组1的开始下标
int i = l;
// 数组2的开始下标
int j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
// 第一个数组已经遍历完毕
arr[k] = aux[j - l];
j ++;
}else if (j > r) {
// 第二个子数组遍历完毕
arr[k] = aux[i - l];
i ++;
}else if (aux[i - l] <= aux[j - l]) {
// 将aux[i - l]写回arr[k]
arr[k] = aux[i - l];
i ++;
}else {
// aux[i - l] > aux[j - l] 写回aux[j - l]
arr[k] = aux[j - l];
j ++;
}
}
}
/**
* 在arr[l..r]上进行插入排序
* @param arr
* @param l
* @param r
*/
private static void insertionSort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
for (int j = i; j >= l + 1 && arr[j] < arr[j - 1]; j--) {
swap(arr,j,j - 1);
}
}
}注意：这是优化后的归并排序，小数组直接使用插入排序能更加优化时间。
因为插入排序在近乎有序的数组时间复杂度很低接近O（n）。
没优化之前的代码可以把此处代码更换掉：
改为：
if(r <= l) return;三、算法稳定性
最核心的merge操作： 需要开辟额外空间，空间大小就是合并后的数组大小
- 先将两个子数组的所有内容复制到新数组中
- 遍历两个子数组，将较小值写回原数组
两边都从头开始遍历，将较小值写回arr数组即可，如下：
四、拓展
4.1 海量数据处理：用到外部存储器
内存只有1G，待排序的数据有100G，该如何对这100G的数据进行排序？
a. 先把这个100G的数据分成200份
b. 分别将0.5G的数据读入内存，进行内部排序（归并，快排，堆排）
c. 进行200个文件的merge操作即可
整个结果就有序了~
4.2 归并排序的衍生问题
归并排序非常适合对链式结构进行排序，链表，二叉树等~
这里有两道💪扣的题目，可以用归并排序分治的思想去思考，下面推给大家：
- 剑指offer 51 ： 数组中的逆序对 (困难)
- 力扣148 ：排序链表 （中等）
总结
以上就是归并排序的图解和代码，有什么疑问可以私信博主~有帮助的话可以关注博主后续更新。
