归并排序
归并排序的思想是分治法+回溯，将一个无序的数组先按照原来的一半进行拆分，一直拆分到最后一个元素，然后开始回溯，排序开始的过程是再回溯时开始排序的。
算法.png
思想总结：
- 将源数组进行拆分，每次拆分一半，由图可以分析出，当arr.length=n,需要拆分log2^8=3次。
- 当拆分到不能再拆分，也就是分组到每个组只有1个元素，停止拆分
- 开始排序并回溯排序，每次排序的时间复杂度为O(n)
- 总的时间复杂度为n x log2^n,时间复杂度不考虑系数和底数，所以n x log2^n等价于 O(nlogn)
==其实归并总结就是2部分 1. 先拆分 2 回溯排序==
代码分析
从分析我们知道，想要实现回溯，那么通常是使用递归的。那么回溯的问题解决了，我们要如何实现O(n)的时间复杂度呢？。以下图i=2对应回溯为例子：
1592837889(1).jpg
如果我们分别对数组arr1={2,3,6,8},和arr2={1,4,5,7}，如果使用选择，插入，冒泡等排序都是O(n^2), 显然最后算法变成n^2*logn。我们可以换个思路：
算法.png
说下回溯的过程：
- 当我们回溯排序时，源数组不变，我们将拆分后的数组历史保存到另外的数组中，如临时数组arr1={2,3,6,8},临时数组arr2={1,4,5,7},临时数组总空间O(n),(源arr的顺序是上次回溯后排序得到的)。
- 然后我们定义几个指针：
left->arr1 起始位置
mid->arr1结束的位置
right->arr2->结束的位置
i指向左边待排序的元素
j指向右边待排序的位置
k指向源数组中排好序的元素的下一个位置(指向新排序元素将要放置的位置)
- left，mid，right作为判断结束的条件，i，j不断移动指向左右数组要排序的元素，k用来作为存放元素的位置
//对数组[l...r] 全闭空间排序
public static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {//只有一个元素了，那么它就是有序的
return;
} else {
//找到中间边界mid 拆分2个数组[l...mid]和[mid+1...r]
int mid = (r - l) / 2 + l;
//左边继续拆分
mergeSort(arr, l, mid);
//右边边继续拆分
mergeSort(arr, mid + 1, r);
//一直拆分到l==r 说明只有一个元素 retuen
//然后开始回溯合并排序
merge(arr, l, mid, r);
}
}
public static void merge(int[] arr, int l, int mid, int r) {
//1. l不一定是从0开始的 2.因为是 对数组[l...r] 全闭空间排序 所以要+1
int[] temp = new int[r - l + 1];
//赋值临时数组 也就是拆分左右数组，将arr拆分成arr1和arr2
for (int i = l; i <= r; i++) {
//上面说过l不是从0开始的 但是我们的temp是0开始的，所以要进行l的偏移
temp[i - l] = arr[i];
}
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
//当arr2排序完成 但是arr1还有元素 那么直接赋值
if (j > r && i <= mid) {
arr[k] = temp[i - l];
i++;
//当arr1排序完成 但是arr2还有元素 那么直接赋值
} else if (i > mid && j <= r) {
arr[k] = temp[j - l];
j++;
} else if (temp[i - l] < temp[j - l]) {
arr[k] = temp[i - l];
i++;
} else {
arr[k] = temp[j - l];
j++;
}
}
}
首先根据代码理解思想。要是还是有点似懂非懂的话。下面这张图应该能帮到你。下面描述的情况是2-2归并。最后左面4个元素有序，右边4个元素有序(对应上面分析图的上一步)
算法.png
归并排序--迭代法
归并排序，还有一种迭代法。递归法归并排序使用的是先自上而下拆分(分治)，再自底向上归并，那么如果我们直接通过递归，将数组按照size=1,2,4,8...n 去拆分，那么合并的数组为arr1-arr2: 1-1.2-2,4-4,8-8...左右两边分别代表arr1和arr2的长度。代码：
/**
* 自定向上排序
*
* @param arr 待排序数组
* @param n 数组的长度
*/
public static void mergeSort(int[] arr, int n) {
/*
* 数组分2层循环 第一层是确定分组后每个组的长度，按照上面图的图示所知
* size分别为1,2,4,8...
* 当size=1 那么arr1.length=1 arr2.length=1 所以 1-1 排序 最终 “每” 2个元素有序
* 当size=2 那么arr1.length=2 arr2.length=2 所以 2-2 排序 最终 “每” 4个元素有序
* 当size=4 那么arr1.length=4 arr2.length=4 所以 4-4 排序 最终 “每” 8个元素有序
* 所以这层循环 就是为了帮助我们创建符合要求变化的size大小
* 最开始数组长度=1 也就是1个元素 他就是有序的 那么size = 2 * size这个算式就帮助我们迭代创建size分别为1,2,4,8...
*
*/
for (int size = 1; size <= n; size = 2 * size) {
/*
*i表示的是每个要合并分作的起始坐标也就是left 我们知道 left-right是通过mid分成arr1和arr2的
* 也就是[l...mid]-[mid+1...r] 等价于[l...size-1]和[size...r]
* 所以i的取值变化为i = i + 2 * size
* 同时i不能越界 所以i<n
*/
for (int i = 0; i + size < n; i = i + 2 * size) {
/*
* 上面分析[l...mid]-[mid+1...r] 等价于[l...size-1]和[size...r]
* 所以 i等价l i + size - 1等价mid i + size + size - 1等价r
* 虽然i<n合法 但是i + size可能越界，
* 同时当i+size>=n说明 只有arr1 arr2为null，那么也就不归并了 他就是有序的
* 因为从上面得知，归并的前提是arr1和arr2是有序的
*
*
* i + size + size - 1相当于r 他可能越界 所以Math.min(i + size + size - 1, n - 1)
*
*/
merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1));
}
}
}
归并排序优化
现在直接上代码
public static void mergeSort(int[] arr, int l, int r) {
if (r-l<=15) {
insertSort(arr,l,r);// 1 .
return;
} else {
//找到中间边界mid 拆分2个数组[l...mid]和[mid+1...r]
int mid = (r - l) / 2 + l;
//左边继续拆分
mergeSort(arr, l, mid);
//右边边继续拆分
mergeSort(arr, mid + 1, r);
//一直拆分到l==r 说明只有一个元素 retuen
//然后开始回溯合并排序
if (arr[mid] > arr[mid + 1])//2.
merge(arr, l, mid, r);
}
}
- 当拆分到足够小的时候选择使用插入排序，原始是插入排序对相对有序的数组效率比较高，所以当数组越小的时候有序的几率就越大，所以使用插入排序
- (arr[mid] <= arr[mid + 1]) 也就是所arr1中的最大的元素已经比arr2最小的元素还要小，那么arr1所有元素就小于等于arr2的所有元素，因为再归并中arr1和arr2都是有序的，那么此时[l...r]就是有序的，所以当(arr[mid] > arr[mid + 1])时我们才需要排序
思考
逆序对 ？
什么是逆序对.逆序对是判断一个数组有序程度的一个标示。一个完全有序的数组，逆序对个数=0
1 2 3 4 5 6 8 7 一个逆序对
利用归并思想，当向上归并：
2 3 6 8 ｜ 1 4 5 7
2与1比较 1<2 那么1比左边2 3 6 8 都要小那么此时逆序对4
继续归并到
1 2 3 当4<6时 4比左边6 8 小 逆序对未2
最终将计数相加
感谢：
https://juejin.im/post/5a96d6b15188255efc5f8bbd
https://juejin.im/post/5ab4c7566fb9a028cb2d9126
https://blog.csdn.net/dugudaibo/article/details/79508198
算法与数据结构-综合提升 C++版
网友评论