《算法导论》Problem 2-4 Inversions
在Merge Sort的基础上改改就好了。
1 public class Inversions { 2 3 public static int inversions(int [] A,int p, int r) 4 { 5 6 if(p<r) 7 { 8 int q = (int) Math.floor( (p+r)/2 ); 9 int left = inversions(A,p,q); 10 int right = inversions(A,q+1,r); 11 int c = combine(A,p,q,r); 12 return left + right + c; 13 } 14 return 0; 15 16 } 17 public static int combine(int [] A, int p, int q, int r) 18 { 19 int total_inversions = 0; 20 21 int n1 = q-p+1; 22 int n2 = r-q; 23 int [] L = new int[n1]; 24 int [] R = new int[n2]; 25 for(int i=0; i<n1; i++) 26 L[i] = A[p+i]; 27 for(int i=0; i<n2;i++) 28 R[i]=A[q+i+1]; 29 30 int i=0; 31 int j=0; 32 int counter = p; 33 while(i<L.length && j<R.length) 34 { 35 if(L[i]<=R[j]) 36 { 37 A[counter]=L[i]; 38 i++; 39 } 40 else 41 { 42 A[counter]=R[j]; 43 j++; 44 total_inversions += (q-(p+i)+1); 45 } 46 counter++; 47 } 48 if(i==L.length) 49 { 50 for(int k=j;k<R.length;k++) 51 A[counter++] = R[k]; 52 } 53 else 54 { 55 for(int k=i;k<L.length;k++) 56 A[counter++] = L[k]; 57 } 58 return total_inversions; 59 } 60 public static void main(String[] args) { 61 int A[] = {2,3,8,6,1,7,9,1}; 62 int num_of_inversions = inversions(A,0,A.length-1); 63 System.out.println(num_of_inversions); 64 } 65 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。