合併排序不工作

我想建立一個算法，我通過合併排序排序鏈接列表。這裏代碼：合併排序不工作

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功能：

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

來源

2016-01-23 Maxim

顯示'merge（）'的來源 –

我同意@JimGarrison：問題很可能在'merge（...）'內（到目前爲止，其餘的排序看起來很好）。從你所描述的內容來看，我懷疑你在將兩個列表合併成一個新列表時遇到了一些問題。測試這種方法的一種方法是，新合併列表的長度爲'start1 + start2'（當然，合併之前）。 – Turing85

您是否在IDE中使用調試器（Eclipse，Idea，NetBeans）？如果是，請設置一個包含五個元素的簡單測試用例，並逐步執行代碼，隨時檢查變量。如果您不使用IDE，請停止，下載並學習使用調試器。這是編寫和調試軟件的要求。 –

合併列表時，你必須與你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），而另一個列表仍然包含元素。

寫一個筆&用你的mergesort和一個已排序的列表進行紙張測試。這應該揭示這個問題。

來源

2016-01-23 23:12:39 Turing85

合併排序不工作

回答

相關問題