병합 알고리즘의 질서수 그룹 합병 알고리즘 실현

병합 알고리즘의 질서수 그룹 합병 알고리즘 실현
간단한 질서수 그룹 합병 알고리즘: 함수를 써서 2개의 질서정연한 정수 그룹을 전송하고 질서정연한 정수 그룹을 되돌려줍니다.상당히 간단하게 이루어진다. 길이가 이 두 길이의 합인 수조를 만든 다음에 각각 세 개의 바늘로 이 세 개의 수조를 가리키고, 이 두 개의 수조 중의 각 요소가 합병 수조의 위치에 있는 것을 찾아서 어떤 수조 바늘이 끝에 도착할 때까지 삽입한다.또 다른 수조의 나머지 모든 원소를 병합수조의 끝에 직접 넣는다.알고리즘의 간단한 실현은 매개 변수에 대한 검사, 수조의 질서 여부를 판단하는 데 주의해야 한다.

public class MergeOrderedArray { 
 public static int[] merge(int [] a,int []b){ 
  if(!isOrderedArray(a)){ 
   System.out.println(" array a is not an ordered array."); 
   return null; 
  } 
    
  if(!isOrderedArray(b)){ 
   System.out.println(" array b is not an ordered array."); 
   return null; 
  } 
   
  int a_len = a.length; 
  int b_len = b.length; 
  int[] merge = new int[a_len+b_len]; 
  int i=0,j=0,k=0; 
  while(i<a_len&&j<b_len){ 
   if(a[i]<b[j]){ 
    merge[k++]=a[i++]; 
   }else{ 
    merge[k++]=b[j++]; 
   } 
  } 
   
  //A , b  
  if(i==a_len){ 
   for(;j<b_len;j++){ 
    merge[k++]= b[j]; 
   } 
  }else{ 
   for(;i<a_len;i++){ 
    merge[k++]= a[i]; 
   } 
  } 
   
  return merge; 
   
 } 
 
 public static boolean isOrderedArray(int [] array){ 
  if(array==null||array.length==0){ 
   return false; 
  } 
   
  for(int i = 0;i<array.length-1;i++){ 
   if(array[i]>array[i+1]){ 
    return false; 
   } 
  } 
  return true; 
 } 
  
 public static void main(String[] args) { 
  int a [] = {1,2,3,4,5}; 
  int b [] = {2,3,4,5,6,7,8,9}; 
  int [] merge = merge(a,b); 
  System.out.println(Arrays.toString(merge)); 
 } 
} 
알고리즘의 시간 복잡도는 합병을 기다리는 두 개의 수조의 길이에 달려 있기 때문에 O(M+N)이고 공간 복잡도도 O(M+N)이다. 즉, 필요한 합병수조의 길이는 M+N이다.
읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!

좋은 웹페이지 즐겨찾기