Go语言视频零基础入门到精通

thinkinjava

代码难看，没时间整理。

/*
为了减少数据移动次数，不妨采用一个临时工作数组temp，
　归并过程中，设置index1，index2和index三个指针，其初值分别指向三个有序区的起始位置。
归并时依次比较temp[index1]和temp[index2]的关键字，取关键字较小的记录复制到arr[index]中，
然后将被复制记录的指针index1或index2加1，以及指向复制位置的指针index加1。
　　重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到arr中即可。
*/
public class MergeSort {   
     static int count=0;
  
    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        // TODO Auto-generated method stub   
        int[] arr = {2,3,6,7,66,77,55,44,66,79,56,37};   
        sort(arr);   
        System.out.println(arr.length);   
        print(arr);   
        System.out.println(count);
        count=0;
        int a[]={8,7,6,5,4,3,2,1};
        sort(a);
        print(a);
        System.out.println(count);
    }   
      
    static void print(int arr[]) {   
        for (int temp : arr) {   
            System.out.printf("%d,",temp);   
        }   
        System.out.println();   
    }   
      
    public static void sort(int arr[]) {   
        int temp[] = new int[arr.length];   
        mergeSort(arr,temp,0,arr.length-1);   
    }   
      
    private static void mergeSort(int arr[],int temp[],int m,int n) {   
        if (m == n) return;   
        int mid = (m+n)/2;   
        mergeSort(arr, temp, m, mid);   
        mergeSort(arr, temp, mid+1, n);   
        for (int i = m; i <= n; i++) {   
            temp = arr;   
        }   
        int index1 = m;   
        int index2 = mid + 1;   
        int index = m;   
           
    /* 归并排序是将数组temp[m,n]分成两半temp[m,mid]和temp[mid+1,n]分别进行归并排序，然后再将这两半合并起来。
       在合并的过程中（设m<=index1<=mid，mid+1<=index2<=n），当temp[index1]<=temp[index2]时，并不产生逆序数；
       当temp[index1]>temp[index2]时，在后面部分中比temp[index1]大的数都比temp[index2]大，逆序数要加上mid+1-index1。
      因此，可以在归并排序中的合并过程中计算逆序数。*/
        while (index1 <= mid && index2 <= n) {   
            if (temp[index1] <= temp[index2]) {   
                arr[index++] = temp[index1++];   
            } else {   
                arr[index++] = temp[index2++];   
                count=count+mid-index1+1;
            }   
        }   
        while(index1 <= mid) {   
            arr[index++] = temp[index1++];   
        }   
        while(index2 <= n) {   
            arr[index++] = temp[index2++];   
        }   
           
    }   
  
}  

C:\java>java MergeSort
12
2,3,6,7,37,44,55,56,66,66,77,79,
17
1,2,3,4,5,6,7,8,
28