java合并排序无法正常工作
我想建立一个算法,通过合并排序对链表进行排序。代码如下:
private Item mergeSort(Item l){
//if the list contains of just one item we don't have to sort it anymore
if(l.next == null) return l;
//divide your list in two parts and get both starts of both lists
Item middle = getMidItem(l);
Item start1 = l;
Item start2 = middle.next;
middle.next = null;
//process recursively the same process but with the both new lists until both lists only contain of one item
Item item1 = mergeSort(start1);
Item item2 = mergeSort(start2);
//if both lists are sorted put them together
return merge(item1, item2);
}
此函数以递归方式工作。首先,如果它没有其他元素,则返回当前元素并停止函数。如果它有多个元素,我将确定元素的中间位置(getMidItem工作正常,我已经调试了好几次),并将两个列表分为两部分。之后,我再次递归地打开函数,并对两个列表执行该操作,直到列表只包含一个元素。如果发生这种情况,我将返回所有元素并合并它们
merge函数确定哪个元素是较小的元素,将较小元素的引用放在前面,将较大元素的引用放在末尾,直到它遍历整个列表。这里的问题是,我的整个结构。如果我运行它,他将到达一个点,列表只包含一个元素,他返回它,保存它,只在最后一个递归步骤中合并并停止它。最后,我没有得到我的列表,只有列表的第一个元素
我意识到这是行不通的,但实际上我不知道如何重写它,使它符合我的要求。我知道合并排序是如何工作的,但我不知道如何实现它,就像这样。在有人说“这很难,只需重写方法体并返回第一个、中间和最后一个,或者使用数组”之前,我必须这样做。这是家庭作业
下面是merge
函数:
public static Item merge(Item a, Item b){
//if both items are null return null, if one is null return the other
if(a == null && b == null) return null;
else if(a == null && b != null) return b;
else if(a != null && b == null) return a;
else{
//create minimum and check if 'a' or 'b' is smaller and set it to minimum
Item min = null;
//if a is smaller than b, a should be returned and the next item of 'a' should be 'b'
if(a.value.compareTo(b.value) < 0){
//the next reference of the smaller element should be the bigger one
min = a;
a = a.next;
}
else{
//same but the other way around
min = b;
b = b.next;
}
//you create the next reference of the minimum
Item p = min;
if(a != null && b != null){
//you iterate through the whole list and put the references of the smaller one on the front and the bigger one behind
while(a.next != null && b.next != null){
if(a.value.compareTo(b.value) < 0){
p.next = a;
a = a.next;
}
else{
p.next = b;
b = b.next;
}
}
}
return p;
}
}
# 1 楼答案
合并列表时,
merge(...)
方法存在逻辑问题:检查是否
a != null && b != null
。如果只有一个列表是null
,会怎么样?在这种情况下,您会忽略第二个列表中的内容,从而导致松散的数据。您必须考虑这样一个事实,即其中一个列表可能会耗尽数据(即isnull
),而另一个列表仍然保存元素做一支笔&;使用合并排序和已排序列表进行纸上测试。这应该揭示问题所在