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)？index 处的元素i从数组中删除，因此之前在 index 处的元素i+1现在位于 index 处i，并且数组大小减小。如果你这样做i++，并且再一次a.remove(i)，你将跳过数组中的一个元素。

在您的sort函数中，调用 时merge，您应该检查a.size() == 0. 你会发现情况并非总是如此。该merge函数看起来不错，但是您的数组拆分不正确：您忘记了 usingremove(int i)更改了数组；它的大小和元素的索引。

于 2012-05-06T08:34:17.253 回答