爱分享版权声明
1. 本站文章和资源均来自互联网收集和整理，本站不承担任何责任及版权问题。
2. 相关版权归作者及其公司所有，仅供学习研究用途，请勿用于商业目的。
3. 若侵犯您的版权，请发邮件至webmaster@ishare1.cn联系我们，我们确认后将立即删除。
什么是归并排序？
归并排序是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
（推荐教程：java快速入门）
实现代码：
import java.util.Arrays;
/**
* @author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
public static void MergeSort(int[] arr, int start, int end) {
//分治的结束条件
if (start >= end) {
return;
}
//保证不溢出取start和end的中位数
int mid = start + ((end - start) >> 1);
//递归排序并且合并
MergeSort(arr, start, mid);
MergeSort(arr, mid + 1, end);
Merge(arr, start, mid, end);
}
//合并
public static void Merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int p1 = start;
int p2 = mid + 1;
int p = 0;
while (p1 arr[p2]) {
temp[p++] = arr[p2++];
} else {
temp[p++] = arr[p1++];
}
}
while (p1
运行结果：
相关视频教程推荐：java视频教程
