归并排序解决小和问题和逆序对问题
2020-12-13 16:29
标签：解法 void 归并排序 system for == bsp col pre 小和问题： 左边比当前元素小的元素的元素的和 暴力解法不推荐O(N^2) 归并加速 归并排序解决小和问题和逆序对问题 标签：解法 void 归并排序 system for == bsp col pre 原文地址：https://www.cnblogs.com/bowenqianngzhibushiwo/p/11620246.html public static void main(String[] args){
int [] a=new int[]{2, 4, 1, 3, 5};
System.out.println( smallSum(a));
}
public static int smallSum(int[] arr) {
if (arr == null || arr.length ) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
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 r) {
//res += arr[p1] //小和
res += arr[p1] > arr[p2] ? (m-p1+1) : 0;//逆序
help[i++] = arr[p1] ];
}
while (p1 m) {
help[i++] = arr[p1++];
}
while (p2 r) {
help[i++] = arr[p2++];
}
for (i = 0; i ) {
arr[l + i] = help[i];
}
return res;
}