爲什麼我的樞軸排序算法沒有達到基本情況？

我得到一個堆棧溢出異常，試圖構造鏈表的排序算法。我的排序無限期地停留在同一個樞軸上，我無法弄清楚它爲什麼沒有達到基本情況。爲什麼我的樞軸排序算法沒有達到基本情況？

// intList中是一個簡單的單向鏈表類的int VAR「.item」等。接下來指針

pivotS(Intlist thisList){ 
    if (thisList == null || thisList.next == null){ 
     return thisList; 
    } else{ 
     int pivot = thisList.item; 
     Intlist lower = lowerThanPivot(pivot, thisList); 
     Intlist upper = greaterOrEqualPivot(pivot, thisList); 
     lower = pivotS(lower); 
     upper = pivotS(upper); 
     return appendLists(lower, upper); 
    } 
    }

這應的工作方式類似於合併排序的建設，對不對？我個人的功能似乎很好。我只是設置遞歸錯誤？

來源

2012-10-30 Frank

哪裏是返回類型。 – Mordechai

你可以發佈lowerThanPivot（）或者greaterOrEqualPivot（）嗎？我認爲這是一個遍歷列表的問題（也許你是通過不重置迭代器或其他東西來跳過元素），看到迭代器內置到實際的列表類中，據我所知，並且你從未提及過除.next和.item以外的任何其他方法 –

此人發現.item嚴格低於pivot的成員。如果（L == null）{ return L; （L.item> = n）{ } return lowerThanPivot（n，L.next）; } else { return new Intlist（L.item，lowerThanPivot（n，L.next））; }} – Frank

假設你有由數字137的兩份名單，讓我們看看這個算法會做。

首先，你想看看第一個元素，並注意它的存在（不爲null），並且列表中不只有一個元素（下一個指針不爲空要麼）。然後，拆分第一個項目爲支點，所以樞軸137

現在，看看接下來會發生什麼。 lower列表由所有小於主元素的元素組成，在本例中爲空列表。該upper列表包含的支點，在這種情況下是兩個137.然後遞歸調用pivotS上都列出了副本的大於或等於所有元素。但是，這裏存在問題 - upper列表與您需要排序的原始列表相同，因此遞歸的執行方式與以前完全相同。這最終導致堆棧溢出。

要修復此問題，請更新代碼以將輸入列表拆分爲三個 groups - 小於pivot的元素，等於pivot的元素和大於pivot的元素。這可能看起來像這樣：

pivotS(Intlist thisList){ 
    if (thisList == null || thisList.next == null){ 
     return thisList; 
    } else{ 
     int pivot = thisList.item; 
     Intlist lower = lowerThanPivot(pivot, thisList); 
     Intlist equal = equalToPivot(pivot, thisList); 
     Intlist upper = greaterThanPivot(pivot, thisList); 
     return appendLists(appendLists(pivotS(lower), equal), pivotS(upper); 
    } 
    }

來源

2015-08-24 23:05:46 templatetypedef

爲什麼我的樞軸排序算法沒有達到基本情況？

回答

相關問題