[java] view plain copy

• package MyGuiBing;  
•   
• public class GuiBingPaiXu {  
•     static int count;//新增  
•     /*
•      * 归并排序+逆序数
•      *  
•      * 与归并排序比较 增加了两行核心代码
•      *  
•      *  
•      * 如果i<j而且 a>a[j]  成为逆序数
•      *  
•      * */  
•   
•     public static void main(String[] args) {  
•         // TODO Auto-generated method stub  
•         //int[] a = { 26,5,77,1,61,11,59,15,48,19 };  
•         //int[] a={4,3,6,5,1,2};  
•         int[] a={2,4,3,1};  
•         sop(a);  
•         Guibing(a, 0, a.length - 1);  
•         sop(a);  
•         System.out.println(count);  
•     }  
•   
•     public static void sop(int[] arr) {  
•         for (int i = 0; i < arr.length; i++) {  
•             System.out.print(arr + "\t");  
•         }  
•         System.out.println();  
•     }  
•   
•     public static void Guibing(int[] n, int first, int last) {  
•   
•         if (first < last) {  
•             int mid = (first + last) / 2;  
•             //左边  
•             Guibing(n, first, mid);  
•             //右边  
•             Guibing(n, mid + 1, last);  
•             //左右归并  
•             Mes(n, first, mid, last);  
•         }  
•     }  
•   
•     public static void Mes(int[] a, int first, int mid, int last) {  
•         int[] temp = new int[a.length];  
•         int i = first;  
•         int j = mid + 1;  
•         int m = mid, n = last;  
•         int k = 0;  
•         //把较小的数先移到新数组中  
•         while (i <= m && j <= n) {  
•             if (a <= a[j]) {  
•   
•                 temp[k++] = a[i++];  
•             } else {  
•                 temp[k++] = a[j++];  
•                 count +=mid-i+1;// 逆序数 核心代码  
•             }  
•   
•         }  
•         //把左边剩余的数先移到新数组中  
•         while (i <= m) {  
•             temp[k++] = a[i++];  
•         }  
•         //把右边剩余的数移到新数组中  
•         while (j <= m) {  
•             temp[k++] = a[j++];  
•   
•         }  
•         //把新数组中的元素 覆盖到 a数组中  
•         for (int p = 0; p < k; p++) {  
•             a[first + p] = temp[p];  
•         }  
•     }  
•   
• }  
  

[java] view plain copy

• package MyGuiBing;  
•   
• public class GuiBingPaiXu {  
•     static int count;//新增  
•     /*
•      * 归并排序+逆序数
•      *  
•      * 与归并排序比较 增加了两行核心代码
•      *  
•      *  
•      * 如果i<j而且 a>a[j]  成为逆序数
•      *  
•      * */  
•   
•     public static void main(String[] args) {  
•         // TODO Auto-generated method stub  
•         //int[] a = { 26,5,77,1,61,11,59,15,48,19 };  
•         //int[] a={4,3,6,5,1,2};  
•         int[] a={2,4,3,1};  
•         sop(a);  
•         Guibing(a, 0, a.length - 1);  
•         sop(a);  
•         System.out.println(count);  
•     }  
•   
•     public static void sop(int[] arr) {  
•         for (int i = 0; i < arr.length; i++) {  
•             System.out.print(arr + "\t");  
•         }  
•         System.out.println();  
•     }  
•   
•     public static void Guibing(int[] n, int first, int last) {  
•   
•         if (first < last) {  
•             int mid = (first + last) / 2;  
•             //左边  
•             Guibing(n, first, mid);  
•             //右边  
•             Guibing(n, mid + 1, last);  
•             //左右归并  
•             Mes(n, first, mid, last);  
•         }  
•     }  
•   
•     public static void Mes(int[] a, int first, int mid, int last) {  
•         int[] temp = new int[a.length];  
•         int i = first;  
•         int j = mid + 1;  
•         int m = mid, n = last;  
•         int k = 0;  
•         //把较小的数先移到新数组中  
•         while (i <= m && j <= n) {  
•             if (a <= a[j]) {  
•   
•                 temp[k++] = a[i++];  
•             } else {  
•                 temp[k++] = a[j++];  
•                 count +=mid-i+1;// 逆序数 核心代码  
•             }  
•   
•         }  
•         //把左边剩余的数先移到新数组中  
•         while (i <= m) {  
•             temp[k++] = a[i++];  
•         }  
•         //把右边剩余的数移到新数组中  
•         while (j <= m) {  
•             temp[k++] = a[j++];  
•   
•         }  
•         //把新数组中的元素 覆盖到 a数组中  
•         for (int p = 0; p < k; p++) {  
•             a[first + p] = temp[p];  
•         }  
•     }  
•   
• }