Java教程
算法入门3-归并排序
归并排序是常见的排序方法，下面介绍归并排序的定义、实现步骤、时间复杂度分析，以及扩展的小和问题、逆序对问题。由归并改造的题目，是面试工作中常考题型，需要重点掌握。
一、定义
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
二、实现步骤
1、将这一组数对半分成两区间；
2、左区间对半分，右区间对半分。左子区间和右子区间继续对半分，依此类推，直到最小区间是只有一个数；
3、从最小区间开始，左右区间开始有序合并。
4、合并的结果层层上提，最终合并成有序数组。
图示：
java代码实现：
// 归并排序
public class MergeSort {
public static void main(String[] args) {
Integer[] arr = DataStore.getData();
String source = "";
for(int i = 0; i < arr.length; i++) {
source += arr[i] + " ";
}
System.out.println("原数组：" + source);
MergeSort.sort(arr, 0, arr.length - 1);
String res = "";
for(int i = 0; i < arr.length; i++) {
res += arr[i] + " ";
}
System.out.println("排序后：" + res);
}
// 归并排序
public static void sort(Integer[] arr, int L, int R) {
MergeSort.sort(arr, L, R);
}
// 二分后合并
public static void process(Integer[] arr, int L, int R) {
if(L == R) {
return;
}
// 等价于L +（R - L）/ 2
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
// 合并
public static void merge(Integer[] arr, int L, int M, int R) {
// 辅助数组，用于存放R - L区间排序后的值
Integer[] help = new Integer[R - L + 1];
// 辅助数组当前位置
int i = 0;
// 左区间当前位置
int p1 = L;
// 右区间当前位置
int p2 = M+1;
// arr[p1]和arr[p2]对比大小，小值放入辅助数组，并自身索引加1
while(p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// 补充，考虑p2已放完，p1未放完的情况
while(p1 <= M) {
help[i++] = arr[p1++];
}
// 补充，考虑p1已放完，p2未放完的情况
while(p2 <= R) {
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
}
DataStore工具类
public class DataStore {
// 随机获取10个整数
public static Integer[] getData() {
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < 10; i++) {
double d = Math.random();
list.add((int)(d*10));
}
Integer[] arrays = new Integer[list.size()];
list.toArray(arrays);
return arrays;
}
// 数组中两数交换
public static void swap(Integer[] array, int i, int j) {
if(array != null && i < array.length && j< array.length) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
输出：
原数组：7 3 7 0 2 3 4 8 8 1
排序后：0 1 2 3 3 4 7 7 8 8
三、时间复杂度分析
归并排序是一个不断二分的过程，从上图容易看到，二分的层数是logN，如数组是8个数，一共分3层进行二分，全部的二分次数是N，所以，归并排序复杂度为O(N*logN)。
归并排序将排序复杂度O(N2) 降为O(NlogN)的本质原因，是因为不浪费每一次的比较结果。实现方式是对半分数据，左排序，右排序，再归并成一条，这一过程不断从小到大递归，最终得到结果。
四、扩展
1、小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：[1, 3, 4, 2, 5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16。
分析：这个题目当然可以用暴力解法，直接遍历每一个数，但时间复杂度是O(N ^ 2)。其实可以用归并法解决，时间复杂度降为O(N*logN)。
先来看，**小和问题可以等价于，把数组中每一个数自身累加，累加的次数为右边比它大的数的个数。**比如题目中的1，右边比它大的数是3、4、2、5，所以1要累加的次数是4。
在经典归并排序实现的基础上，解答小和问题，实现步骤：
1）merge方法内，当arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，因为这样才能保证arr[p1]比arr[p2]小时，（R-p2+1）一定是右区间的数比arr[p1]大的个数；
2）merge方法内，当arr[p1] < arr[p2]时，累加(R - p2 + 1) * arr[p1]结果，这里的意思是把一个数自身累加，累加的次数为右边比它大的数的个数；
3）将累加结果不断递归返回。
java实现代码：
// 归并法求小和
public class MergeSortSmallSum {
public static void main(String[] args) {
// 小和值：2 + 1 + 2 + 1 = 6
Integer[] arr = {2,1,4,3};
String source = "";
for(int i = 0; i < arr.length; i++) {
source += arr[i] + " ";
}
System.out.println("原数组：" + source);
Integer smallSum = MergeSortSmallSum.process(arr, 0, arr.length - 1);
String res = "";
for(int i = 0; i < arr.length; i++) {
res += arr[i] + " ";
}
System.out.println("排序后：" + res);
System.out.println("小和：" + smallSum);
}
// 二分后归并
public static Integer process(Integer[] arr, int L, int R) {
if(L == R) {
return 0;
}
// 等价于L +（R - L）/ 2
int mid = L + ((R - L) >> 1);
return process(arr, L, mid)
+ process(arr, mid + 1, R)
+ merge(arr, L, mid, R);
}
// 归并，并计算小和
public static Integer merge(Integer[] arr, int L, int M, int R) {
// 辅助数组，用于存放R - L区间排序后的值
Integer[] help = new Integer[R - L + 1];
// 辅助数组当前位置
int i = 0;
// 左区间当前位置
int p1 = L;
// 右区间当前位置
int p2 = M+1;
int res = 0;
while(p1 <= M && p2 <= R) {
// 求小和等效于，把数组中每一个数自身累加，累加的次数为右边比它大的数的个数
// 右区间已排好序，所以当arr[p1]比arr[p2]小时，右区间的数比arr[p1]大的个数是（R-p2+1）
res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
// arr[p1]和arr[p2]对比大小，小值放入辅助数组，并自身索引加1
// 与经典merge过程不一样的地方，这里arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，
// 因为这样才能保证arr[p1]比arr[p2]小时，（R-p2+1）一定是右区间的数比arr[p1]大的个数
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 补充，考虑p2已放完，p1未放完的情况
while(p1 <= M) {
help[i++] = arr[p1++];
}
// 补充，考虑p1已放完，p2未放完的情况
while(p2 <= R) {
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
}
}
输出：
原数组：2 1 4 3
排序后：1 2 3 4
小和：6
2、逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
分析：同样的，这个题目可以用暴力解法，直接遍历每一个数，但时间复杂度仍然是O(N ^ 2)。同样，我们用归并法解决，时间复杂度降为O(N*logN)。
在经典归并排序实现的基础上，解答逆序对问题，实现步骤：
1）merge方法内，当arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，因为这样才能保证arr[p1]比arr[p2]大时，（R-p2+1）一定是右区间的数比arr[p1]小的个数；
2）merge方法内，当arr[p1] > arr[p2]时，累加(R - p2 + 1)的结果，即逆序对的个数，并遍历arr[p2]到arr[R]的数，打印逆序对；
3）将累加结果不断递归返回。
java实现代码：
// 归并法求逆序对
public class MergeSortReverse {
public static void main(String[] args) {
// 逆序对：{2,1} {4,3}
Integer[] arr = {2,1,4,3};
String source = "";
for(int i = 0; i < arr.length; i++) {
source += arr[i] + " ";
}
System.out.println("原数组：" + source);
Integer count = MergeSortReverse.process(arr, 0, arr.length - 1);
String res = "";
for(int i = 0; i < arr.length; i++) {
res += arr[i] + " ";
}
System.out.println("排序后：" + res);
System.out.println("逆序对数：" + count);
}
// 二分后合并
public static Integer process(Integer[] arr, int L, int R) {
if(L == R) {
return 0;
}
// 等价于L +（R - L）/ 2
int mid = L + ((R - L) >> 1);
return process(arr, L, mid) +
process(arr, mid + 1, R) +
merge(arr, L, mid, R);
}
// 合并
public static Integer merge(Integer[] arr, int L, int M, int R) {
// 辅助数组，用于存放R - L区间排序后的值
Integer[] help = new Integer[R - L + 1];
// 辅助数组当前位置
int i = 0;
// 左区间当前位置
int p1 = L;
// 右区间当前位置
int p2 = M+1;
// 逆序对数
int count = 0;
// arr[p1]和arr[p2]对比大小，大值放入辅助数组，并自身索引加1
while(p1 <= M && p2 <= R) {
// 右区间已排好序，所以当arr[p1]比arr[p2]大时，右区间的数比arr[p1]小的个数是（R-p2+1）
if(arr[p1] > arr[p2]) {
count += (R - p2 + 1);
for(int k = p2; k <= R; k++) {
System.out.println("逆序对：{" + arr[p1] + "," + arr[k] + "}");
}
}
// arr[p1]和arr[p2]对比大小，大值放入辅助数组，并自身索引加1
help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
}
// 补充，考虑p2已放完，p1未放完的情况
while(p1 <= M) {
help[i++] = arr[p1++];
}
// 补充，考虑p1已放完，p2未放完的情况
while(p2 <= R) {
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return count;
}
}
输出：
原数组：2 1 4 3
逆序对：{2,1}
逆序对：{4,3}
排序后：4 3 2 1
逆序对数：2
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
