递归算法(3)

1. **  
2.  *  
3.  * @author SunnyMoon  
4.  */  
5.   
6. /**  
7.  * 概念介绍：  
8.  *   
9.  * 归并排序：归并算法的中心是归并两个已经有序的数组，并且递归调用归并操作。  
10.  *   
11.  * 归并排序优点和缺点：比简单排序在速度上快很多；归并排序会占用双倍的存储空间。  
12.  *   
13.  * 归并排序的效率：归并排序的时间复杂度是 O(N*LogN)；简单排序的复杂度是O(N2)。  
14.  */  
15. public class Recursion3 {   
16.   
17.     private long[] theArray;   
18.     private int nElems;   
19.   
20.     public Recursion3(int max) {//初始化数组   
21.         theArray = new long[max];   
22.         nElems = 0;   
23.     }   
24.   
25.     public void insert(long value) {//插入数据   
26.         theArray[nElems] = value;   
27.         nElems++;   
28.     }   
29.   
30.     public void display() {//显示数组中的数据   
31.         for (int j = 0; j < nElems; j++) {   
32.             System.out.print(theArray[j]+","+" ");   
33.         }   
34.     }   
35.     /**  
36.      * 归并排序算法  
37.      */  
38.     public void mergeSort() {   
39.         long[] workSpace = new long[nElems];//创建一个工作数组，用于排序操作使用   
40.         recMergeSort(workSpace, 0, nElems - 1);//执行归并排序操作   
41.     }   
42.        
43.     /**  
44.      * 递归分割数据到基本单位  
45.      */  
46.     private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {   
47.         if (lowerBound == upperBound) {   
48.             return;   
49.         } else {   
50.             int mid = (lowerBound + upperBound) / 2;   
51.             recMergeSort(workSpace, lowerBound, mid);   
52.             recMergeSort(workSpace, mid + 1, upperBound);   
53.             merge(workSpace, lowerBound, mid + 1, upperBound);   
54.         }   
55.     }   
56.        
57.     /**  
58.      * 归并操作将基本单位归并成整个有序的数组  
59.      */  
60.     private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {   
61.         int j = 0;   
62.         int lowerBound = lowPtr;   
63.         int mid = highPtr - 1;   
64.         int n = upperBound - lowerBound + 1;   
65.   
66.         while (lowPtr <= mid && highPtr <= upperBound) {   
67.             if (theArray[lowPtr] < theArray[highPtr]) {   
68.                 workSpace[j++] = theArray[lowPtr++];   
69.             } else {   
70.                 workSpace[j++] = theArray[highPtr++];   
71.             }   
72.         }   
73.             while (lowPtr <= mid) {   
74.                 workSpace[j++] = theArray[lowPtr++];   
75.             }   
76.             while (highPtr <= upperBound) {   
77.                 workSpace[j++] = theArray[highPtr++];   
78.             }   
79.             for (j = 0; j < n; j++) {   
80.                 theArray[lowerBound + j] = workSpace[j];   
81.             }   
82.     }   
83.     public void println(String str){   
84.             System.out.println(str);   
85.         }   
86. }   
87.   
88. class MergeSortApp {//主程序   
89.   
90.     public static void main(String[] args) {   
91.         int maxSize = 100;   
92.         Recursion3 arr = new Recursion3(maxSize);   
93.         /**  
94.          * 插入值到数组  
95.          */  
96.         arr.insert(64);   
97.         arr.insert(21);   
98.         arr.insert(11);   
99.         arr.insert(33);   
100.         arr.insert(12);   
101.         arr.insert(85);   
102.         arr.insert(44);   
103.         arr.insert(99);   
104.         arr.insert(3);   
105.         arr.insert(0);   
106.         arr.insert(108);   
107.         arr.insert(36);   
108.            
109.         arr.println("显示排序前数据：");   
110.         arr.display();   
111.         arr.println("");     
112.            
113.         arr.mergeSort();   
114.            
115.         arr.println("显示排序后数据：");   
116.         arr.display();   
117.         arr.println("");     
118.     }   
119. }   
120. /**  
121.  *   
122.  * 显示排序前数据：  
123.  * 64, 21, 11, 33, 12, 85, 44, 99, 3, 0, 108, 36,   
124.  * 显示排序后数据：  
125.  * 0, 3, 11, 12, 21, 33, 36, 44, 64, 85, 99, 108,  
126.  */  
127.   
128. /**  
129.  * 总结：  
130.  * 归并排序比简单排序的效率高很多，把递归发挥的淋漓尽致，大家可以试一下。  
131.  * 最后给出归并排序工作过程图解。  
132.  */