归并排序-使用归并排序实现小和问题-java实现

什么是归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法，它的基本思想是将待排序的序列不断地分割成两个子序列，直到每个子序列只有一个元素，然后再将这两个子序列合并成一个有序的序列。

归并排序的基本步骤如下：

1.将待排序序列分成两个子序列，分别进行排序。
2.将两个已排序的子序列合并成一个有序的序列。
3.重复步骤1和步骤2，直到所有元素都排序完成。
归并排序的时间复杂度为 O(nlogn)，是一种稳定的排序算法。1. 1. *

利用归并排序解决一道实际的算法题.小和问题

题目:
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数 组的小和。求一个数组的小和
示例:
输入：[5 3 2 4 9]
输出：19
解释：
5左边比它小的元素之和为0,
3左边比它小的元素之和为0，
2左边比它小的元素之后为0,
4左边比他小的元素之后为3+2=5,
9左边比他小的元素之后为5+3+2+4=14,
所以最终结果为：0 + 0 + 0 + 5 + 14 = 19

解题思路

其实也很简单,只要你了解了归并排序,那么在归并排序的过程时,我们需要合并拆分的两个数组,那么在合并的过程中,比较下左右两边数字的大小,符合左边比右边小的数字就加起来,就实现了小和问题,实际就在归并排序的基础上增加了一行代码.

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

开始写递归方法

	// 所有merge时，产生的小和，累加
	// 左 排序   merge
	// 右 排序  merge
	// merge
	public static int process(int[] arr, int l, int r) {
		if (l == r) {
			return 0;
		}
		// l < r
		int mid = l + ((r - l) >> 1);
		return 
				process(arr, l, mid) 
				+ 
				process(arr, mid + 1, r) 
				+ 
				merge(arr, l, mid, r);
	}

再来实现merge 计算和排序的过程

public static int merge(int[] arr, int L, int m, int r) {
		int[] help = new int[r - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = m + 1;
		int res = 0;
		while (p1 <= m && p2 <= r) {
			res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while (p1 <= m) {
			help[i++] = arr[p1++];
		}
		while (p2 <= r) {
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
		return res;
	}