import java.util.Scanner; public class Main { static int[]a; static int[]temp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); a=new int[n]; temp=new int[n+1]; for (int i = 0; i < n; i++) a[i]=sc.nextInt(); long ans = mergeSort(a, 0, n-1); System.out.println(ans); } static long mergeSort(int []a, int left, int right) { //定义终止条件 if (left >= right) return 0; //求中间值 int mid = (left + right) >> 1; //不断进行递归,使得数组呈现有序递增 long count = mergeSort(a, left, mid) + mergeSort(a, mid + 1, right); //i为左数组下标,j为右数组下标,pos为临时数组下标 int i = left, j = mid + 1; int pos = 1; while (i <= mid && j <= right) { //如果a[i]<a[j],那么A[j]时右数组中第一个大于a[i]的元素,a在左右两数组是升序的, //那么从mid+1到j-1的元素都小于a[i],则a[i]逆序数为j-mid-i if (a[i] <= a[j]) { temp[pos] = a[i]; ++i; count += (j - mid) - 1; } else { temp[pos] = a[j]; ++j; } pos++; } //左数组是否全部遍历 for (int k = i; k <= mid; k++) { temp[pos++] = a[k]; count += (j - mid) - 1; } //右数组是否全部遍历 for (int k = j; k <= right; k++) temp[pos++] = a[k]; pos = 1; //复制数组 for (int k = left; k <= right; k++,pos++) { a[k] = temp[pos]; } return count; } }
0.0分
2 人评分
汽水瓶 (C语言代码)浏览:610 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:647 |
C二级辅导-计负均正 (C语言代码)浏览:658 |
C语言训练-字符串正反连接 (C语言代码)浏览:622 |
简单的for循环浏览:1412 |
WU-printf基础练习2 (C++代码)浏览:2007 |
【金明的预算方案】 (C++代码)浏览:940 |
【明明的随机数】 (C语言代码)浏览:788 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:564 |
出圈】指针malloc版浏览:355 |