算法导论Java实现-合并排序（包含习题2.3-2）

 

1. package lhz.algorithm.chapter.two; 
2.  
3. /** 
4.  * 《合并排序》，利用分治思想进行排序。（针对习题2.3-2） 
5.  * 《算法导论》原文摘要： 
6.  * The  merge sort algorithm closely follows the divide -and-conquer paradigm . Intuitively, it  
7.  *  operates as follows.  
8.  * •   Divide: Divide the  n-element sequence to be sorted into two subsequences of  n/2  
9.  *     elements each.  
10.  * •   Conquer: Sort the two subsequences recursively using merge sort.  
11.  * •   Combine: Merge the two sorted subsequences to produce the sorted answer.  
12.  * The recursion "bottoms out" when the sequence to be sorted has length 1,  in which case there  
13.  * is no work to be done, since every sequence  of length 1 is already in sorted order.  
14.  * The key operation of the merge sort algorithm is  the merging of two sorted sequences in the  
15.  * "combine" step. To perform the merging,  we use an auxiliary procedure MERGE( A,  p,  q,  r ),  
16.  * where A is an array and  p,  q, and r  are indices numbering elements of the array such that  p ≤  q <  r . The procedure assumes that the subarrays  A[p  q] and A[q + 1   r ] are in sorted order.  
17.  * It  merges  them to form a single sorted subarray that replaces the current subarray  A[p  r].  
18.  *  
19.  * Our MERGE procedure takes time Θ ( n), where n = r - p + 1 is the number of 
20.  * elements being merged, and it works as follows. Returning to our card-playing 
21.  * motif , suppose we have two piles of cards face up on a table. Each pile is 
22.  * sorted, with the smallest cards on top. We wish to merge the two piles into a 
23.  * single sorted output pile, which is to be face down on the table. Our basic 
24.  * step consists of choosing the smaller of the two cards on top of the face-up 
25.  * piles, removing it from its pile (which exposes a new top card), and placing 
26.  * this card face down onto the output pile. We repeat this step until one input 
27.  * pile is empty, at which time we just take the remaining input pile and place 
28.  * it f ace down onto the output pile. Computationally, each basic step takes 
29.  * constant time, since we are checking just two top cards. Since we perform at 
30.  * most n basic steps, merging takes Θ( n) time. 
31.  *  
32.  * 伪代码： 
33.  *  MERGE(A, p, q, r)  
34.  *1  n1  ← q -  p + 1  
35.  *2  n2  ← r -  q  
36.  *3  create arrays  L[1   n1  + 1] and  R[1   n2  + 1]  
37.  *4  for  i ← 1  to n1   
38.  *5       do L[i] ← A[p +  i - 1]  
39.  *6  for  j ← 1  to n2   
40.  *7       do R[j] ← A[q +  j]  
41.  *8  L[n1  + 1] ← ∞ （∞代表到达最大值，哨兵位） 
42.  *9  R[n2  + 1] ← ∞  
43.  *10  i ← 1  
44.  *11  j ← 1  
45.  *12  for  k ← p to r  
46.  *13       do if  L[i] ≤ R[j]  
47.  *14              then A[k] ← L[i]  
48.  *15                   i ← i + 1  
49.  *16              else A[k] ← R[j]  
50.  *17                   j ← j + 1  
51.  *@author lihzh(苦逼coder) 
52.  */ 
53. public class MergeSort { 
54.      
55.     private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 }; 
56.  
57.     /** 
58.      * @param args 
59.      */ 
60.     public static void main(String[] args) { 
61.         mergeSort(input); 
62.         //打印数组 
63.         printArray(); 
64.     } 
65.      
66.     /** 
67.      * 针对习题2.3-2改写，与伪代码不对应 
68.      * @param array 
69.      * @return 
70.      */ 
71.     private static int[] mergeSort(int[] array) { 
72.         //如果数组的长度大于1，继续分解数组 
73.         if (array.length > 1) { 
74.             int leftLength = array.length / 2; 
75.             int rightLength = array.length - leftLength; 
76.             //创建两个新的数组 
77.             int[] left = new int[leftLength]; 
78.             int[] right = new int[rightLength]; 
79.             //将array中的值分别对应复制到两个子数组中 
80.             for (int i=0; i<leftLength; i++) { 
81.                 left[i] = array[i]; 
82.             } 
83.             for (int i=0; i<rightLength; i++) { 
84.                 right[i] = array[leftLength+i]; 
85.             } 
86.             //递归利用合并排序，排序子数组 
87.             left = mergeSort(left); 
88.             right = mergeSort(right); 
89.             //设置初始索引 
90.             int i = 0; 
91.             int j = 0; 
92.             for (int k=0; k<array.length; k++) { 
93.                 //如果左边数据索引到达边界则取右边的值 
94.                 if (i == leftLength && j < rightLength) { 
95.                     array[k] = right[j]; 
96.                     j++; 
97.                 //如果右边数组索引到达边界，取左数组的值 
98.                 } else if (i < leftLength && j == rightLength) { 
99.                     array[k] = left[i]; 
100.                     i++; 
101.                 //如果均为到达则取，较小的值 
102.                 } else if (i < leftLength && j < rightLength) { 
103.                     if (left[i] > right[j]) { 
104.                         array[k] = right[j]; 
105.                         j++; 
106.                     } else { 
107.                         array[k] = left[i]; 
108.                         i++; 
109.                     } 
110.                 }  
111.             } 
112.         }  
113.         return array; 
114.         /* 
115.          * 复杂度分析： 
116.          * 由于采用了递归，设解决长度为n的数组需要的时间为T(n)，则分解成两个长度为n/2的子 
117.          * 数组后，需要的时间为T(n/2)，合并需要时间Θ(n)。所以有当n>1时，T(n)=2T(n/2)+Θ(n), 
118.          * 当n=1时，T(1)=Θ(1) 
119.          * 解这个递归式，设Θ(1)=c,(c为常量)，则Θ(n)=cn。 
120.          * 有上式可得T(n/2)=2T(n/4)+Θ(n/2),T(n/4)=2T(n/8)+Θ(n/4)....依次带入可得 
121.          * 所以可以有T(n)=nT(1)+Θ(n)+2Θ(n/2)+4Θ(n/4)...+(2^lgn)Θ(n/(2^lgn)),其*有lgn个Θ(n)相加。 
122.          * 即T(n)=cn+cnlgn 
123.          * 所以，时间复杂度为：Θ(nlgn) 
124.          */ 
125.     } 
126.      
127.     private static void printArray() { 
128.         for (int i : input) { 
129.             System.out.print(i + " "); 
130.         } 
131.     } 
132. } 

转自木石大哥的博客    http://mushiqianmeng.blog.51cto.com/#