【好记性不如烂笔头】排序算法之归并排序（三）小和问题_算法小和问题

---

前言

  上篇博客学习了归并排序，一种是遍历的方式实现，一种是迭代的方式实现，那么归并排序的思路只能用于排序嘛？也不是，这篇博客就记录一下归并排序对于求小和问题的思路与写法。

小和

  在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。假设有这样一个数组 [3,4,1,5,2] 求这个数组的小和是多少？

  按照小和的定义：

• 3：左侧没有比3小的数，没有小和。
• 4：左侧有一个3比4小，有小和 3 。
• 1：左侧没有比1小的数，没有小和。
• 5：左侧有3、4、1比5小，有小和3+4+1 。
• 2：左侧有一个1比2小，有小和 1 。
• 数组的小和：3+3+4+1+1=12 。

思考

暴力

   循环整个数组，依次左侧小于当前值的数累加起来。

---

引申

  暴力循环可以解决问题，但每次都要从头再次循环判断，性能有点低啊，有没有什么方法可以避免呢？先找一下规律吧。

• 3：比4小统计了一次，比5小统计了一次，总共统计了2次
• 4：比5小，统计了1次
• 1：比5小统计了一次，比2小统计了一次，总共统计了2次
• 5：右侧没有更大的了
• 2：右侧没有更大的了

  这个有点眼熟啊，3跟4比，1跟5比，3和4 跟 1和5 比，上篇博客的合并merge 好像可以用上啊，上面的这个数组弄的不好，3、4有序了，1、5有序了，重新弄个数组说明吧：

• 3：无
• 2：无
• 4：3+2
• 1：无
• 5：3+2+4+1
• 6：3+2+4+1+5
• 3：2+1
• 0：无
• （3+2）+（3+2+4+1）+（3+2+4+1+5）+（2+1）= 33
• 3个1、4个2、3个3、2个4、1个5

按照merge的思路：

第一次操作产生了：5

第二次操作产生了：2+3

第三次操作产生了：1+1+1+2+2+2+3+3+4+4

总结：5+（2+3）+（1+1+1+2+2+2+3+3+4+4）= 33

3个1、4个2、3个3、2个4、1个5

和暴力解析一致，啊哈，这种迭代排序不必暴力循环快多了。

思路

  merge有实现小和的可能，可是该怎么实现呢？合并就不再画图了，直接说思路：

• 固定流程：左组和右组比较，左数小于右数，记录一次左数
• 我需要一个数ans记录本次小和。
• 我需要一个返回值，返回merge小和。
• 我需要递归操作累加小和，merge返回的小和每次都要参加运算。

代码

	public static int smallSum(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}
		return splitSorting(arr, 0, arr.length - 1);
	}

	public static int splitSorting(int[] arr, int l, int r) {
		// 递归终止条件
		if (l == r) {
			return 0;
		}
		int m = (l + r) / 2;
		// 对于左侧来说，l到中点
		// 对于右侧来说，中点+1到右侧
		return splitSorting(arr, l, m) + splitSorting(arr, m + 1, r) + merge(arr, l, m, r);
	}

	// 我需要一个返回值返回小和
	public static int merge(int[] arr, int L, int M, int R) {
		// 我需要一个数组存放数据
		int[] narr = new int[R - L + 1];
		// 我需要三个指针，分别指向三个数据的头
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		// 我需要一个循环体,结束条件是其中一个越界了,这里写的是循环条件哦，不是结束条件
		// p1,p2都在各自的范围内
		// 我需要一个ans记录小和
		int ans = 0;
		while (p1 <= M && p2 <= R) {
			ans += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
			narr[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		// p1 越界，p1添加完了，剩下数据的就是p2
		while (p2 <= R) {
			narr[i++] = arr[p2++];
		}
		// p2 越界，p2添加完了，剩下数据的就是p1
		while (p1 <= M) {
			narr[i++] = arr[p1++];
		}
		// 合并后的narr数据，要放到原来的数组arr里的
		for (int j = 0; j < narr.length; j++) {
			// L为左侧数据的开始，从L开始放数据
			arr[L + j] = narr[j];
		}
		return ans;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

注意

  上面的代码不完全是和上次一样的，特别需要提示一个地方，上次写的合并代码中，这个位置是小于等于，而本次的合并代码中，这个位置是小于，区别在于

• 上次的重点在排序，相等了谁前谁后没关系。
• 这次的重点在求和，只要小于的，相等的不能再加进去交换了。