2 개의 정렬 된 목록을 재귀 적으로 병합하여 병합 된 목록을 정렬하는 방법

Question

재귀에 대해 배우고 있습니다. 2 개의 정렬 된 목록을 병합하여 정렬 된 목록을 반환하려고 시도하고 있습니다. 나는 이것이 이미 부정확하다는 것을 알고 있지만 어떤 지침이 도움이 될 것입니다.

public static ArrayList<Integer> mergeMyList(ArrayList<Integer> list1, 
      ArrayList<Integer> list2) 
{ 
    ArrayList<Integer> tempList = null; 
    int n = list1.size() +list2.size(); 
    int l = list2.size(); 

    if (n == 0 && l == 0) 
    {       
     tempList = list1; 
     return tempList; 
    } 
    if (n == 0) 
    {       
     tempList = list2; 
     return tempList; 
    } 
    if (l == 0) 
    {       
     tempList = list1; 
     return tempList; 
    } 

    else 
    { 
     int x = list1.get(0); 
     int y = list2.get(0); 

     if (x < y) 
     { 
      // list1.add(x); 
      // list1.add(y); 
      tempList=list1; 
      // list1.remove(0); 
      // list2.remove(0);  

     } 
     else 
     { 
      list1.add(y);      
      tempList = list1; 
      list1.remove(0); 
      list2.remove(0); 
      tempList = mergeMyList(list1,list2); 
     }     
    } 
    tempList = mergeMyList(list1,list2); 
    return tempList; 
} 

Answer 1

단락이 나 더 좋을 수도 있지만 이해할 수있을 것 같습니다.

ArrayList<Integer> mergeList(ArrayList<Integer> list1, 
          ArrayList<Integer> list2) 
{ 
    ArrayList result = new ArrayList<Integer>(); 

    while (list1.size() > 0 && list2.size() > 0) 
    { 
    if (list1.get(0) < list2.get(0)) 
     result.add(list1.remove(0)); 
    else 
     result.add(list2.remove(0)); 
    } 

    while (list1.size() > 0) result.add(list1.remove(0)); 
    while (list2.size() > 0) result.add(list2.remove(0)); 

    return result; 
} 

ArrayList<Integer> QuickSort(ArrayList<Integer> list) 
{ 
    if (list.size() < 2) 
    return list; 

    ArrayList<Integer> left = list.subList(0, list.szie()/2); 
    ArrayList<Integer> right = list.subList(list.szie()/2, 8); 

    return mergeList(QuickSort(left), QuickSort(right)); 
} 

이것은 재귀적인 quicksort의 전체 예제입니다. 그것은 빠르지 만, 많은 공간이 필요하며 목록이 너무 크면 스택을 오버플로 할 수 있습니다.

재귀 병합 :

ArrayList<Integer> mergeList(ArrayList<Integer> list1, 
          ArrayList<Integer> list2) 
{ 
    if (list1.size() == 0) return list2; 
    if (list2.size() == 0) return list1; 

    ArrayList result = new ArrayList<Integer>(); 

    if (list1.get(0) < list2.get(0)) 
    result.add(list1.remove(0)); 
    else 
    result.add(list2.remove(0)); 

    result.addAll(mergeList(list1, list2)); 

    return result; 
}