现在的位置: 首页 > 综合 > 正文

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

2013年11月13日 ⁄ 综合 ⁄ 共 5147字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 

  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/#
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞