<>并归排序&&小和问题&&逆序对问题
原创
<>并归排序&&小和问题&&逆序对问题
原创
master公式的使用
T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
master公式（也称主方法）是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法，（补充：分治策略的递归解法还有两个常用的方法叫做代入法和递归树法，以后有机会和亲们再唠），众所周知，分治策略中使用递归来求解问题分为三步走，分别为分解、解决和合并。
其中 a >= 1 and b > 1 是常量，其表示的意义是n表示问题的规模，a表示递归的次数也就是生成的子问题数，b表示每次递归是原来的1/b之一个规模，f（n）表示分解和合并所要花费的时间之和。
一.并归排序
思路，先把左边一半排序好，再把右边一部分排序好，最后将两部分合并起来就行了。merge的时候采用外排的方法，将排序好的放在一个临时的数组里面，然后在将这个临时数组的内容复制到原来的数组即可。
public void mergeSort(int[] arr,int left,int right){
if (left >= right) return;
int mid = left + ((right - left)>>1);
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
public void merge(int [] array,int left,int mid,int right){
int[] arr = new int[right - left +1];
int i = left;
int j = mid+1;
int index = 0;
while (i <= mid && j <= right){
arr[index++] = array[i]<array[j]?array[i++]:array[j++];
}
while (i <= mid){
arr[index++] = array[i++];
}
while (j <= right){
arr[index++] = array[j++];
}
//复制数组
for (int n = 0;n<arr.length;n++){
array[n+left] = arr[n];
}
}二.小和问题
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
2.思路
1 3 4 2 5
划分为：1 3 4 | 2 5
划分为：1 3 4 | 2 5
划分为：1 3 | 4 | 2 | 5
划分为：1 | 3 | 4 | 2 | 5 这个其实就是归并排序的过程，在每次比较之后，找到右边有多少个数大于左边的。
3.解法
public int smallSum(int [] array,int left ,int right){
if (left == right){
return 0;
}
int mid = left + (right - left)/2;
return smallSum(array,left,mid) +
smallSum(array,mid+1,right) +
smallSumMerge(array,left,mid,right);
}
public int smallSumMerge(int [] array, int left ,int mid ,int right){
int i = left;
int j = mid+1;
int [] help = new int[right - left +1];
int index = 0;
int result = 0;
while (i <= mid && j <= right){
result += array[i]<array[j] ? (right - j + 1)*array[i]:0;
help[index++] = array[i]<array[j] ? array[i++] : array[j++];
}
while (i <= mid){
help[index++] = array[i++];
}
while (j <= right){
help[index++] = array[j++];
}
for (int n = 0 ; n < help.length ; n++){
array[left+n] = help[n];
}
return result;
}三.逆序对问题
ArrayList<Pair<Integer,Integer>> result = new ArrayList<>();
public void InversePairs(int [] array,int left ,int right){
if (left == right){
return ;
}
int mid = left + (right - left)/2;
InversePairs(array,left,mid);
InversePairs(array,mid+1,right);
InversePairsMerge(array,left,mid,right);
}
public void InversePairsMerge(int [] array, int left ,int mid ,int right){
int i = left;
int j = mid+1;
int [] help = new int[right - left +1];
int index = 0;
while (i <= mid && j <= right){
if (array[i]>array[j]){
for (int mm = i;mm<=mid;mm++){
result.add(new Pair<>(array[mm],array[j]));
}
}
help[index++] = array[i]<array[j] ? array[i++] : array[j++];
}
while (i <= mid){
help[index++] = array[i++];
}
while (j <= right){
help[index++] = array[j++];
}
for (int n = 0 ; n < help.length ; n++){
array[left+n] = help[n];
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
