Java合併兩個有序序列演算法的實作範例

這篇文章主要介紹了Java實現合併兩個有序序列演算法,簡單描述了序列合併演算法的原理與java合併有序序列的具體操作步驟及相關實現技巧,需要的朋友可以參考下

本文實例講述了Java實作合併兩個有序序列演算法。分享給大家供大家參考，具體如下：

問題描述

#輸入：序列A，其中a0輸出：序列B,其中b0

##演算法思想

建立一個長度為r的陣列R，將A中的序列視為兩個有序序列

#B=A

C=A

分別由B和C中拿取一個數字來比較，將較小的放入R，如果這個數在B中，則繼續取B中下一個最小的數；如果在C中，同樣操作。所有數字都在R中。

Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)如果B或C沒有更多的數可以取得，則將另一個序列的所有數填製R。

Ri=(MIN(B)MIN(C))

#演算法實作

/**
 *
 * @author Chuck
 *
 */
public class Merge {
  /**
   * 合并两个有序序列
   * @param A 待合并序列
   * @param q 第二个序列开始数组下标
   * @return 合并后的新数组
   */
  public static int[] merge(int [] A,int q){
    //创建数组
    int n = A.length;
    int [] R = new int[n];
    int i = 0;
    int j = q+1;
    int k = 0;
    //如果两个数组B 和 C中都有数据则选择更小的加入到R中并获取下一个
    while(i<=q&&j<=n-1){
      if(A[i]<=A[j]){
        R[k]=A[i];
        i++;
      }else{
        R[k]=A[j];
        j++;
      }
      k++;
    }
    //如果B中有数据则把所有数据加入到R中
    while(i<=q) R[k++] = A[i++];
    //如果C中有数据则把所有数据加入到R中
    while(j<n-1) R[k++] = A[j++];
    return R;
  }
  public static void main(String [] args){
    int [] A = {5,6,7,8,9,44,55,66,788,1,3,10,45,59,70,188};
    int q = 8;
    int [] R = Merge.merge(A, q);
    for(int i=0;i<R.length;i++){
      System.out.print(R[i] +" ");
    }
  }
}

演算法時間

#######f(n)=q+1+r−q=r+1# ########這裡的r是陣列的輸入規模，所以演算法最壞情況運行時間為：#########f(n)=O(n)###### #########示範結果##################

1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788

以上是Java合併兩個有序序列演算法的實作範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！