java - 合并排序不能递归地工作

Question

我想构建一个算法，通过合并排序对链表进行排序。代码如下:

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 工作正常，我已经调试了几次)并将两个列表分为两部分。之后，我再次递归地打开该函数并对两个列表执行此操作，直到列表仅包含一个元素。如果发生这种情况，我将返回所有元素并合并它们。

合并函数确定哪个元素较小，将较小元素的引用放在前面，将较大元素放在最后，直到遍历整个列表。这里的问题是我的整个结构。如果我运行它，他将到达一个点，其中列表仅包含一个元素，他返回它，保存它并仅在最后一个递归步骤中合并并停止它。最后，我没有得到我的列表，而只得到列表的第一个元素。

我意识到这行不通，但我实际上不知道如何重写它，以便它达到我想要的效果。我知道合并排序是如何工作的，但我不知道如何实现它，就像这样。在有人说“这样很难，只需重写方法体并返回第一个、中间和最后一个或使用数组来完成”之前，我必须这样做。这是家庭作业。

这是合并函数:

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;
    }
}

Answer 1

合并列表时，您的 merge(...) 方法存在逻辑问题:

   if(a != null && b != null){ // PROBLEM OCCURS HERE
        //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){ // AND HERE
            if(a.value.compareTo(b.value) < 0){
                p.next = a;
                a = a.next;
            }
            else{
                p.next = b;
                b = b.next;
            }
        }
    }

您检查是否a != null && b != null。如果只有一个列表为 null 怎么办？在这种情况下，您会忽略第二个列表中的内容，因此会丢失数据。您必须考虑这样一个事实:其中一个列表可能会耗尽数据(即 null)，而另一个列表仍包含元素。

使用合并排序和已排序的列表进行笔和纸测试。这应该可以揭示问题。