我一直在尝试实现递归合并排序而感到头疼,但我不断遇到问题。 现在,我在添加元素时遇到了很多麻烦,这导致了我之前 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);
}
}
主要问题又是不断困扰我的合并部分,特别是将元素添加到临时列表中。编译器向我抛出越界异常。
最佳答案
问题是
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--;
}
关于java - LinkedList 上的递归合并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24623143/