逆序数
分析
- 逆序数的意义：就是选择排序中对元素交换的次数。
- 普通的比较时间复杂度都是O(N^2)，肯定是不能通过的。
- 需要一种O(NlgN)的排序算法
利用归并排序
import java.io.*;
import java.util.*;
public class modp {
public static int sum =0;
public static int a[] = new int[50010];
public static int b[] = new int[50010];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = 0;
n = in.nextInt();
for(int i=0;i<n;i++) {
a[i] = in.nextInt();
}
merge_sort(0, n-1);
out.println();
out.flush();
}
public static void merge_sort(int low, int high) {
if(low >= high)
return ;
int mid = (low + high) / 2;
merge_sort(low, mid);
merge_sort(mid+1, high);
merge(low, mid, high);
}
public static void merge(int low, int mid, int high) {
int i = low;
int j = mid+1;
for(int k=low;k<=high;k++) {
b[k] = a[k];
}
for(int k=low;k<=high;k++) {
if(i > mid)
b[k] = a[j++];
else if(j > high)
b[k] = a[i++];
else if(a[i] <= a[j])
b[k] = a[i++];
else {
b[k] = a[j++];
sum += mid-i+1; //from i to mid,all numbers are bigger than j.
}
}
for(int k=low;k<=high;k++) { //error1:忘记对原数组重新赋值
a[k] = b[k];
}
}
}
/*
4
2
4
3
1
*/
代码的效率还是不高
运行时间.png
收获
eclipse设置断点
设置断点.png
-
在该行最右边行数处点击右键，选择Toggle Breakpoint。
debug.png - 点击小虫子图标，进入Debug模式
- F5：Step into/进入该行的函数内部
F6：Step over/一行一行执行
F7：Step return/退出当前的函数
