0

文字列の配列リストにマージソートアルゴリズムを実装しようとしていますが、配列リストの順序を台無しにしているバグを見つけることができないようです。

private static void sort(java.util.ArrayList<String> a)
{

   // End recursion
   if (a.size() < 2)
   {
      return;
   }


   int mid = a.size() / 2;


   java.util.ArrayList<String> left = new java.util.ArrayList<String>();


   int i;

   for (i = 0; i < mid; i++)
   {

      left.add(a.remove(i));

   }


   java.util.ArrayList<String> right = new java.util.ArrayList<String>();

   // Copy the second half to the "right"
   for ( ; i < a.size(); i++)
   {
      right.add(a.remove(i));
   }


   sort(left);
   sort(right);

   merge(a, left, right);
}

private static void merge(java.util.ArrayList<String> result, java.util.ArrayList<String> left,java.util.ArrayList<String> right)
{
   int i, l, r;

   i = l = r = 0;


   while (l < left.size() && r < right.size())
   {
      if ((left.get(l)).compareTo(right.get(r)) < 0)
      {
         result.add(left.get(l));
         l++;
      }
      else
      {
         result.add(right.get(r));
         r++;
      }

      i++;
   }


   while (l < left.size())
   {
      result.add(left.get(l));
      l++;
      i++;
   }

   // Append rest of the values in the right half, if any...
   while (r < right.size())
   {
      result.add(right.get(r));
      r++;
      i++;
   }  
}
4

1 に答える 1

1

問題はsort関数にあります。

使用するとどうなりますa.remove(i)か？インデックスの要素iが配列から削除されるため、以前はインデックスにあった要素がi+1インデックスiになり、配列のサイズがデクリメントされます。その後i++、a.remove(i)を実行すると、配列内の1つの要素がスキップされます。

sort関数で、を呼び出すときはmerge、それを確認する必要がありますa.size() == 0。常にそうであるとは限らないことがわかります。関数は問題ないように見えますが、配列の分割が正しくありません。使用すると配列が変更mergeされることを忘れています。remove(int i)そのサイズとその要素のインデックス。

于 2012-05-06T08:34:17.253 に答える