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

javalearner

并归排序：
  将两个或两个以上的有序数组组合成一个新的有序数组，叫并归排序

排序过程
1、 设初始数组有n个数据，则可看成n个有序的子数组，
        每个子数组长度为1；
2、 两两合并，得到n/2或n/2+1 个长度为2 或1 的有序子数组；
3、 再两两合并，…… 如此重复，直至得到一个长度为n 的
        有序数组为止。
   
  
   
  
  
  下面是并归排序的递归实现：

1. class DArray
   
2.    {
   
3.    private long[] theArray;          // ref to array theArray
   
4.    private int nElems;               // number of data items
   
5.    public DArray(int max)            // constructor
   
6.       {
   
7.       theArray = new long[max];      // create array
   
8.       nElems = 0;
   
9.       }
   
10.    public void insert(long value)    // put element into array
    
11.       {
    
12.       theArray[nElems] = value;      // insert it
    
13.       nElems++;                      // increment size
    
14.       }
    
15.    public void display()             // displays array contents
    
16.       {
    
17.       for(int j=0; j< nElems; j++)    // for each element,
    
18.          System.out.print(theArray[j] + " ");  // display it
    
19.       System.out.println("");
    
20.       }
    
21.    public void mergeSort()           // called by main()
    
22.       {                              // provides workspace
    
23.       long[] workSpace = new long[nElems];
    
24.       recMergeSort(workSpace, 0, nElems-1);
    
25.       }
    
26.    private void recMergeSort(long[] workSpace, int lowerBound,
    
27.                                                int upperBound)
    
28.       {
    
29.       if(lowerBound == upperBound)            // if range is 1,
    
30.          return;                              // no use sorting
    
31.       else
    
32.          {                                    // find midpoint
    
33.          int mid = (lowerBound+upperBound) / 2;
    
34.                                               // sort low half
    
35.          recMergeSort(workSpace, lowerBound, mid);
    
36.                                               // sort high half
    
37.          recMergeSort(workSpace, mid+1, upperBound);
    
38.                                               // merge them
    
39.          merge(workSpace, lowerBound, mid+1, upperBound);
    
40.          }  // end else
    
41.       }  // end recMergeSort()
    
42.    private void merge(long[] workSpace, int lowPtr,
    
43.                            int highPtr, int upperBound)
    
44.       {
    
45.       int j = 0;                             // workspace index
    
46.       int lowerBound = lowPtr;
    
47.       int mid = highPtr-1;
    
48.       int n = upperBound-lowerBound+1;       // # of items
    
49.       while(lowPtr <= mid && highPtr <= upperBound)
    
50.          if( theArray[lowPtr] < theArray[highPtr] )
    
51.             workSpace[j++] = theArray[lowPtr++];
    
52.          else
    
53.             workSpace[j++] = theArray[highPtr++];
    
54.       while(lowPtr <= mid)
    
55.          workSpace[j++] = theArray[lowPtr++];
    
56.       while(highPtr <= upperBound)
    
57.          workSpace[j++] = theArray[highPtr++];
    
58.       for(j=0; j< n; j++)
    
59.          theArray[lowerBound+j] = workSpace[j];
    
60.       }  // end merge()
    
61.   
    
62.    }  // end class DArray
    
63. class MergeSortApp
    
64.    {
    
65.    public static void main(String[] args)
    
66.       {
    
67.       int maxSize = 100;             // array size
    
68.       DArray arr;                    // reference to array
    
69.       arr = new DArray(maxSize);     // create the array
    
70.       arr.insert(64);                // insert items
    
71.       arr.insert(21);
    
72.       arr.insert(33);
    
73.       arr.insert(70);
    
74.       arr.insert(12);
    
75.       arr.insert(85);
    
76.       arr.insert(44);
    
77.       arr.insert(3);
    
78.       arr.insert(99);
    
79.       arr.insert(0);
    
80.       arr.insert(108);
    
81.       arr.insert(36);
    
82.       arr.display();                 // display items
    
83.       arr.mergeSort();               // merge sort the array
    
84.       arr.display();                 // display items again
    
85.       }  // end main()
    
86.    }  // end class MergeSortApp
    

复制代码

运行结果：
C:java>java MergeSortApp
64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108
   
     
     
      
      

        
      

        
      
     
   
  
  









源码下载：http://file.javaxxz.com/2014/10/30/235930546.zip