2.2.19倒置。编写一个线性对数级别的算法统计给定数组中的"倒置"数量(即插入排序所需的交换次数,请见2.1节)。这个数量和Kendall tau距离有关，请见2.5节。

答：参考资料：

1)Kendall tau距离定义的简单理解：有两个排列L1,L2，两个排列的长度相同，两个排列中的元素相同，并且在同一个排列中元素不重复时,L1排列中所有位置i<j时两元素排列的集合CL1与L2排列中所有位置i<j时两元素排列集合CL2的　|(CL1 并 CL2)-(CL1 交 CL2)|/2.

2)代码：

import java.util.Arrays;

public class E2d2d19

{

    private static Comparable[] aux;

    public static long sort(Comparable[] a)

    {

        aux=new Comparable[a.length];

        return sort(a,0,a.length-1);

    }

    private static long sort(Comparable[] a,int lo,int hi)

    {

        long inversion=0;

        if (hi<=lo) return inversion;

        int mid=lo+(hi-lo)/2;

        inversion=inversion+sort(a,lo,mid);

        inversion=inversion+sort(a,mid+1,hi);

        inversion=inversion+merge(a,lo,mid,hi);

        return inversion;

    }

   

    private static long merge(Comparable[] a,int lo,int mid,int hi)

    {

        long inversion=0;

       

        int i=lo,j=mid+1;

        for (int k=lo;k<=hi;k++)

        aux[k]=a[k];

       

        for(int k=lo;k<=hi;k++)

        if        (i>mid) a[k]=aux[j++];

        else if (j>hi)    a[k]=aux[i++];

        else if (less(aux[j],aux[i])) {a[k]=aux[j++];inversion=inversion+(mid-i+1);}

        else            a[k]=aux[i++];

       

        return inversion;

      }

    private static boolean less(Comparable v,Comparable w)

    { return v.compareTo(w)<0;}

     public static boolean isSorted(Comparable[] a)

    {

      for(int i=1;i<a.length;i++)

        if(less(a[i],a[i-1])) return false;

      return true;

    }

    

   public static void main(String[] args)

   {

       Integer[] a={6,5,4,3,2,1,0};

       StdOut.printf("reverse inversion=%d\n",sort(a));

       //

       Integer[] b={0,1,2,3,4,5,6};

       StdOut.printf("identical  inversion=%d\n",sort(b));

        //

       Integer[] c={6,5,4,1,1,0};

       StdOut.printf("other inversion=%d\n",sort(c));

   }

}