求小和问题

问题描述
对于一个数组例如，2,1,5,8,9,6,3,4。其中2和5,8,9,6,3,4都会产生小和2，同理1与5,8,9,6,3,4也都会产生小和1，依次累加所有的小和然后返回。
解决方案
      第一种解决方案是，我们直接遍历每个位置上的数，并累加在其左边且比他小的所有的数的总和。最终得到我们的结果
      第二种解决方案是，我们对于每个数都计算出在它右边的且比它大的所有数的个数，然后该位置上的数乘以它右边的且比它大的所有数的个数，就计算出了这个数所能产生的所有小和
      我们采用第二种解决方案。结合归并排序的特点，我们发现小和只有在merge的过程中才会产生，并且只有当左边位置的数字小于右边位置上的数字的时候就会产生小和，因为在merge的过程中，左右两边的数组都是有序的，所以在本次merge过程中该数字产生小和的个数可以通过坐标来计算得出。一个有序数组内不产生任何小和（因为我们已经在之前的merge过程中计算过了）。这样做我们就不会把小和重复计算。
举例说明

第三次的归并调用过程中，整个数组只有两个元素，即两个有序数组，我们发现左边有序数组中只有一个数字，右边有序数组也只有一个数字，并且左边有序数组的数字大于右边有序数组的数字，因此在第三次归并merge的时候不产生任何小和。
第三次归并调用结束后的结果是1,2,5,8,9,6,3,4

第四次归并调用，整个数组同样只有两个元素，我们发现左边有序数组中仅有的一个值是小于右边有序数组中的值的，因此在第四次归并merge过程中产生一个5的小和。

第四次归并调用完成后，数组中的值为1,2,5,8,9,6,3,4

第二次归并merge的过程中，由于1<5，那么将会产生两个1的小和，2<5，将会产生两个2的小和。
第二次归并调用返回后，数组中的值为1,2,5,8,9,6,3,4
第五次归并调用会产生第六次归并调用，而第六次归并调用将会对只含有一个元素的数组进行调用，而对于一个元素进行归并调用将会直接返回，所以忽略掉该次调用。

在第六次归并的merge的过程中，由于9 大于6，所以不产生任何小和。第六次归并调用完成后，数组中的内容为1,2,5,8,6,9,3,4

在第七次归并调用过程中，不产生任何小和。

在第五次归并调用返回的时候不产生任何小和。
第一次归并调用的merge，对于1将会产生4个1的小和，对于2来说，将会产生4个2的小和，对于5来说，将会产生2个5个小和，对于8来说，将会产生1个8的小和。
总计产生了44个小和。
代码编写

#include <iostream>

using namespace std;


// 实现数组的打印
void printArray(int *arr, int length)
{
	for (int i = 0; i < length; ++i)
	{
		printf("%d\t", arr[i]);
	}
	printf("\n");
}

// 实现两个数的交换
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

// 实现的外排算法
int merge(int *arr, int left, int mid, int right)
{
	int *tempArr = new int[right - left + 1];
	int i = 0;
	int p1 = left;
	int p2 = mid + 1;
	int res = 0;
	while (p1 <= mid && p2 <= right)
	{
		if (arr[p1] < arr[p2])
		{
			res += arr[p1] * (right - p2 + 1);
		}
		*(tempArr + i++) = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
	}

	while (p1 <= mid)
	{
		*(tempArr + i++) = arr[p1++];
	}
	while (p2 <= right)
	{
		*(tempArr + i++) = arr[p2++];
	}
	for (int j = 0; j < right - left + 1; ++j)
	{
		arr[left + j] = *(tempArr + j);
	}
	delete[] tempArr;
	return res;
}


int SortProcess(int *arr, int left, int right)
{
	if (left < right)
	{
		int mid = left + ((right - left) >> 1);

		return SortProcess(arr, left, mid) +
			SortProcess(arr, mid + 1, right) +
			merge(arr, left, mid, right);
	}
	return 0;
}
// 壳子函数

int getSmallSum(int *arr, int length)
{
	if (arr == nullptr || length < 2)
	{
		return -1;
	}
	return SortProcess(arr, 0, length - 1);
}

int main(int argc, char **argv)
{
	int arr[] = { 2,1,5,8,9,6,3,4 };
	int length = sizeof(arr) / sizeof(arr[0]);
	printArray(arr, length);
	int res = getSmallSum(arr, sizeof(arr) / sizeof(arr[0]));
	cout << res << endl;
	printArray(arr, length);
	system("pause");
	return 0;
}

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92