Java-分治算法-白红宇

Java-分治算法

阅读量：5222 次

发布时间：2019-06-14

本文共 3161 字，大约阅读时间需要 10 分钟。

一、分治算法的原理

分治算法就是将一个规模为N的问题分解成K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可以得出原问题的解

二、分治算法的伪代码实现

合并算法Merge

1 MERGE(A, p, q, r) 2    n1 ← q - p + 1 3    n2 ← r - q 4    create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1] 5    for i ← 1 to n1 6         do L[i] ← A[p + i - 1] 7    for j ← 1 to n2 8         do R[j] ← A[q + j] 9    L[n1 + 1] ← ∞10    R[n2 + 1] ← ∞11   i ← 112   j ← 113   for k ← p to r14        do if L[i] ≤ R[j]15              then A[k] ← L[i]16                   i ← i + 117              else A[k] ← R[j]18                   j ← j + 1

分治算法：包括“分治”和“合并”

1 MERGE-SORT(A, p, r)2  if p < r3    then q ← ┕(p + r)/2┙4         MERGE-SORT(A, p, q)5         MERGE-SORT(A, q + 1, r)6         MERGE(A, p, q, r)

三、分治算法的Java代码实现

1 import java.util.Arrays; 2 import java.util.Comparator; 3  4  5 public class MergeSort { 6  7     /** 8      * 定义合并方法merge、mergesort方法 9      * 用泛型方法实现10      */11     public static 
     
       void merge(T[] t, int p, int q, int r, Comparator
       c)12     {13         T[] left = Arrays.copyOfRange(t, p, q);14         T[] right = Arrays.copyOfRange(t, q, r);15         16         int indexleft = 0;17         int indexright = 0;18         19         for(int i = p; i < r; i++)20         {21             //注意：这里只看算法了，就完全没管终止条件，要不然indexleft的值不断往上走，肯定会越界的，因为整个程序是从p到r的，而且22             //indexleft和indexright还不一定哪个先结束呢，先结束了的话就没法比较了，就需要针对剩下的做个处理了。。。23             //表示left到头了24             if(indexleft >= left.length)25             {26                 break;27             }28             //表示right到头了29             if(indexright >= right.length)30             {31                 System.arraycopy(left, indexleft, t, i, left.length-indexleft);  32                 break;33             }34             if (c.compare(left[indexleft], right[indexright]) < 0)35             {36                 t[i] = left[indexleft];37                 indexleft++;38             }39             else40             {41                 t[i] = right[indexright];42                 indexright++;43             }44         }45     }46     47     public static 
      
        void mergeSort(T[] t, int p, int r, Comparator
        c) 48     {49         if(p+1 < r)50         {51             int q = (p + r)/2;52             mergeSort(t, p, q, c);53             mergeSort(t, q, r, c);54             merge(t, p, q, r, c);55         }56     }57     58     public static 
       
         void mergeSort(T[] t, Comparator
         c)59     {60         mergeSort(t, 0, t.length, c);61     }62     63     /**64      * @param args65      */66     public static void main(String[] args) {67         // TODO Auto-generated method stub68         Integer[] ints = new Integer[]{2, 0, 5, 23, 1, 4, 8, 56, 19};69         mergeSort(ints, new Comparator
        
         (){70             public int compare(Integer o1, Integer o2){71                 return o1 - o2;72             }73         });74         75         for (int i = 0; i < ints.length; i++)76         {77             System.out.print(ints[i] + " ");78         }79         System.out.println();80     }81 82 }