0

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;
}
4

1 に答える 1

0

ショートかそれ以上でもいいのですが、理解できると思います。

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));
}

これは、再帰的なクイックソートの完全な例です。これは (ある程度) 高速ですが、大量のスペースが必要であり、リストが大きすぎるとスタックがオーバーフローする可能性があります。

再帰的マージ:

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;  
}
于 2013-02-16T17:15:41.160 に答える