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

javalearner

代码难看，没时间整理。

1. /*
   
2. 为了减少数据移动次数，不妨采用一个临时工作数组temp，
   
3. 　归并过程中，设置index1，index2和index三个指针，其初值分别指向三个有序区的起始位置。
   
4. 归并时依次比较temp[index1]和temp[index2]的关键字，取关键字较小的记录复制到arr[index]中，
   
5. 然后将被复制记录的指针index1或index2加1，以及指向复制位置的指针index加1。
   
6. 　　重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到arr中即可。
   
7. */
   
8. public class MergeSort {   
   
9.      static int count=0;
   
10.   
    
11.     /**  
    
12.      * @param args  
    
13.      */  
    
14.     public static void main(String[] args) {   
    
15.         // TODO Auto-generated method stub   
    
16.         int[] arr = {2,3,6,7,66,77,55,44,66,79,56,37};   
    
17.         sort(arr);   
    
18.         System.out.println(arr.length);   
    
19.         print(arr);   
    
20.         System.out.println(count);
    
21.         count=0;
    
22.         int a[]={8,7,6,5,4,3,2,1};
    
23.         sort(a);
    
24.         print(a);
    
25.         System.out.println(count);
    
26.     }   
    
27.       
    
28.     static void print(int arr[]) {   
    
29.         for (int temp : arr) {   
    
30.             System.out.printf("%d,",temp);   
    
31.         }   
    
32.         System.out.println();   
    
33.     }   
    
34.       
    
35.     public static void sort(int arr[]) {   
    
36.         int temp[] = new int[arr.length];   
    
37.         mergeSort(arr,temp,0,arr.length-1);   
    
38.     }   
    
39.       
    
40.     private static void mergeSort(int arr[],int temp[],int m,int n) {   
    
41.         if (m == n) return;   
    
42.         int mid = (m+n)/2;   
    
43.         mergeSort(arr, temp, m, mid);   
    
44.         mergeSort(arr, temp, mid+1, n);   
    
45.         for (int i = m; i <= n; i++) {   
    
46.             temp[i] = arr[i];   
    
47.         }   
    
48.         int index1 = m;   
    
49.         int index2 = mid + 1;   
    
50.         int index = m;   
    
51.            
    
52.     /* 归并排序是将数组temp[m,n]分成两半temp[m,mid]和temp[mid+1,n]分别进行归并排序，然后再将这两半合并起来。
    
53.        在合并的过程中（设m<=index1<=mid，mid+1<=index2<=n），当temp[index1]<=temp[index2]时，并不产生逆序数；
    
54.        当temp[index1]>temp[index2]时，在后面部分中比temp[index1]大的数都比temp[index2]大，逆序数要加上mid+1-index1。
    
55.       因此，可以在归并排序中的合并过程中计算逆序数。*/
    
56.         while (index1 <= mid && index2 <= n) {   
    
57.             if (temp[index1] <= temp[index2]) {   
    
58.                 arr[index++] = temp[index1++];   
    
59.             } else {   
    
60.                 arr[index++] = temp[index2++];   
    
61.                 count=count+mid-index1+1;
    
62.             }   
    
63.         }   
    
64.         while(index1 <= mid) {   
    
65.             arr[index++] = temp[index1++];   
    
66.         }   
    
67.         while(index2 <= n) {   
    
68.             arr[index++] = temp[index2++];   
    
69.         }   
    
70.            
    
71.     }   
    
72.   
    
73. }  
    

复制代码

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

  


源码下载：http://file.javaxxz.com/2014/12/2/000632750.zip