第二章 算法基础 思考题2-4（逆序对）

  1 package chap02;
  2 
  3 import static org.junit.Assert.*;
  4 
  5 import java.util.Arrays;
  6 
  7 import org.junit.Test;
  8 
  9 public class ques2_4 {
 10     /**
 11      * 逆序对，将一个序列中的所有逆序对打印输出
 12      * 
 13      * @author xiaojintao
 14      * 
 15      */
 16     static void printReverseOrder(int[] n) {
 17         int i = 0;
 18         int j;
 19         while (i < n.length - 1) {
 20             for (j = i + 1; j < n.length; j++) {
 21                 if (n[i] > n[j]) {
 22                     System.out.println("<" + n[i] + "," + n[j] + ">");
 23                 }
 24             }
 25             i++;
 26         }
 27     }
 28 
 29     @Test
 30     public void testName() throws Exception {
 31         int[] a = { 2 };
 32         printReverseOrder(a);
 33     }
 34 
 35     /**
 36      * 修改归并排序，使之打印出序列中的所有逆序对数
 37      * 
 38      * @param n
 39      */
 40     static void printReverseByMergeSort(int[] n) {
 41         int start = 0;
 42         int end = n.length;
 43         mergeSort(n, start, end);
 44         ;
 45     }
 46 
 47     @Test
 48     public void test() throws Exception {
 49         int[] a = { 2, 3, 8, 6, 1, 5, 4, 0 };
 50         printReverseByMergeSort(a);
 51     }
 52 
 53     /**
 54      * 修改的归并排序算法用于逆序对输出
 55      * 
 56      * @param a
 57      * @return
 58      */
 59     protected static void mergeSort(int[] a, int start, int end) {
 60         if (start < end - 1) {
 61             int mid = (start + end) / 2;
 62             mergeSort(a, start, mid);
 63             mergeSort(a, mid, end);
 64             merge(a, start, mid, end);
 65         }
 66     }
 67 
 68     /**
 69      * 输出逆序对
 70      * 
 71      * @param a
 72      * @param b
 73      * @return
 74      */
 75     protected static void merge(int[] n, int start, int mid, int end) {
 76         int[] l = Arrays.copyOfRange(n, start, mid);
 77         int[] r = Arrays.copyOfRange(n, mid, end);
 78         int i = 0;
 79         int j = 0;// j<mid-start
 80         int k = 0;// k<end-mid
 81         while (i < end - start) {
 82             if (j < mid - start & k < end - mid) {
 83                 if (l[j] < r[k]) {
 84                     n[i + start] = l[j];
 85                     j++;
 86                 } else {
 87                     System.out.println("<" + l[j] + "," + r[k] + ">");
 88                     n[i + start] = r[k];
 89                     k++;
 90                 }
 91             } else if (k < end - mid) {
 92                 n[i + start] = r[k];
 93                 k++;
 94             } else if (j < mid - start) {
 95                 n[i + start] = l[j];
 96                 j++;
 97             }
 98             i++;
 99         }
100     }
101 }