杭电6318（归并排序）逆序数（java）

归并排序是采用分冶实现的，其核心思想就是分冶得到两边经过递归是有序的，（因为分到最后就是两个元素的比较。

• 举个例子 a[]={7 ,5, 3, 2, 6, 9, 4, 1}进行归并排序
  1： sort（7 5 3 2） sort（6 9 4 1）
  2：递归循环sort（7 5） sort(3 2)
• 看下归并怎么处理sort（7 5）.最后递归sort（7），sort（5）返回7 和5；7和5两个元素是有序的，a[0]=7;a[1]=5;新建数组b[2]; 5的序列标签为i;7的标签为j;其实这个都是0.但是5这边的元素小，所以b[0]=5;此时j ；b[1]=5;再将b数组的元素复制到a[0-1]中。
• 再看sort（7，5，3，2）经过递归处理a[]前四位变成{5，7，2，3}；依然是分左右两份处理。新建数组b[];左面标签i,右面j；5>2；b[0]=2; (j=1).又5>3;所以b[1]=3；右侧没元素，b[2]=5;b[3]=7;（这里ij只是表示左右位数的index）。再将a【】替换。
• 最后整个排序就完成了。这个就是牺牲空间提升速度（个人感觉）；

那么归并排序和逆序数有什么关系呢？

• 仔细观察序列。（7，5）一个逆序列。（3，2）3在二前面，一个逆序。总计两个。（5，7，2，3）2前面两个，三前面两个。总计2 4=6；你可以发现规律：逆序数 =左侧剩余元素数量（前提是当前最小为右侧元素，要操作右侧元素）。层层叠加，就形成了逆序数合。

附上代码如下：
杭电6318

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main { static long time=0; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); long n=0,x=0,y=0; while(in.nextToken() != StreamTokenizer.TT_EOF) { n=(int)in.nval;in.nextToken(); x=(int)in.nval;in.nextToken(); y=(int)in.nval; int a[]=new int[(int) n]; for(int i=0;i<n;i++) { in.nextToken(); a[i]=(int)in.nval; } time=0;long min=x<y?x:y; sort(a,0,a.length-1); long value=min*time; out.println(value); out.flush(); } } public static int[] sort(int a[],int left,int right) { int mid=(left+right)/2; if(left<right) { sort(a,left,mid); sort(a,mid+1,right); merge(a,left,mid,right);} return a; } private static void merge(int[] a, int left, int mid, int right) { int team[]=new int[right-left+1]; int i=left; int j=mid+1; int k=0; while(i<=mid&&j<=right) { if(a[i]<=a[j]) {team[k++]=a[i++];} else { team[k++]=a[j++];time+=mid-i+1; } } while(i<=mid) { team[k++]=a[i++]; } while(j<=right) { team[k++]=a[j++]; } for(int q=0;q<k;q++) { a[q+left]=team[q]; } }
}



  

 

  
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
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/81368317