归并排序求逆序数

归并排序的基本思想

归并排序是一种另一类排序方法。所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。归并排序

的基本思想是将一个具有n个待排序记录的序列看成是n个长度为1的有序列，然后进行两两归并，得到「n/2

个长度为2的有序序列，再进行两两归并，得到「n/4 个长度为4的有序序列，如此重复，直至得到一个长度为

n的有序序列为止。


public class fds {

/**
* @param args
*/
public static int asd=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={9,6,7,2,4,3,5,1};
mergeSort(a,0,7);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
System.out.print(asd);

}
public static void mergeSort(int[] array,int low,int height){  
        if(low>=height)return;  
        int mid = (low+height)/2; 
        mergeSort(array,low,mid); 
        mergeSort(array,mid+1,height); 
        merge(array,low,mid,height); 
    }  
      
    public static void merge(int[] array,int low,int mid,int height){  
        int i,j,h,k;  
        int[] temp = new int[array.length];  
        i=low;  
        h=low;  
        j=mid+1;  
          
        while(h<=mid&&j<=height){  
            if(array[h]<array[j]){  
                temp[i] = array[h];  
                h++;

            }else{  
                temp[i] = array[j];  
                j++;  
               //计算逆序数，整个解题代码就是在这里多加了一行代码。
                  //其余都是归并排序的代码。
                asd+=(mid-h+1);
            }  
            i++;  
        }  
          
        if(j>height){  
            for(k=h;k<=mid;k++){  
                temp[i] = array[k];  
                i++;  
            }  
        }else{  
            for(k=j;k<=height;k++){  
                temp[i] = array[k];  
                i++;  
            }  
        }  
        for(k=low;k<=height;k++){  
            array[k] = temp[k];  
        } 

}
}