java - LinkedList 上的递归合并排序

Question

我一直在尝试实现递归合并排序而感到头疼，但我不断遇到问题。现在，我在添加元素时遇到了很多麻烦，这导致了我之前 75% 的问题。这是实现的代码，主要问题是合并部分:

 static public void DoMerge(LinkedList <Contacto> L, int left, int mid, int right)
 {
     LinkedList <Contacto> temp = new LinkedList <Contacto>();
   int i, left_end, num_elements, tmp_pos, comp;

   left_end = (mid - 1);
   tmp_pos = left;
   num_elements = (right - left + 1);

   while ((left <= left_end) && (mid <= right))
   {
       comp= L.get(left).get_name().compareTo(L.get(mid).get_name());
       if (comp<=0)
       temp.add(tmp_pos++,L.get(left++));
       else
       temp.add(tmp_pos++,L.get(mid++));
   }

   while (left <= left_end)
    temp.add(tmp_pos++,L.get(left++));

   while (mid <= right)
    temp.add(tmp_pos++,L.get(mid++));

   for (i = 0; i < num_elements; i++)
   {
       L.set(right, temp.get(right));
       right--;
   }

}static public void MergeSort_Recursive(LinkedList <Contacto> L, int left, int right)
{
 int mid; 
if (right > left)
 {
   mid = (right + left) / 2;
   MergeSort_Recursive(L, left, mid);
   MergeSort_Recursive(L, (mid + 1), right);
   DoMerge(L, left, (mid+1), right);
 }
}

主要问题又是不断困扰我的合并部分，特别是将元素添加到临时列表中。编译器向我抛出越界异常。

Answer 1

问题是

LinkedList <Contacto> temp = new LinkedList <Contacto>();

您初始化了一个空列表。但是，这一行:

temp.add(tmp_pos++,L.get(left++));

您将一个对象插入索引 tmp_pos，它可以大于 temp 的当前大小(首先，temp 的大小为零)。 (阅读更多关于 add. 的信息)

你可以通过了解，对于合并排序，temp 实际上被用作堆栈来解决这个问题，所以这部分不是必需的 temp.add(tmp_pos++,L.get(left++ ));，请改用 temp.add(L.get(left++));。 (以类似方式替换其他语句)。

对于最后一部分，只需使用

 for (i = 0; i < num_elements; i++)
 {
       L.set(right, temp.removeLast());
       right--;
 }