是否有將每個列表元素分隔到自己的列表中的非遞歸方式？

我正在關注合併排序中的維基百科的僞代碼（以及其他網頁，如sortvis.org和sorting-algorithm.com），並看到合併準備使用遞歸。
我很好奇，看看是否有非遞歸的方式來做到這一點。
也許像for each i element in list, i=[i-th element]。是否有將每個列表元素分隔到自己的列表中的非遞歸方式？

我的印象是遞歸正在保它到一個最小，因爲-in在不良，等於是我想到這個問題。

以下是合併排序的維基百科遞歸部分的僞代碼示例：

function merge_sort(list m) 
    // if list size is 1, consider it sorted and return it 
    if length(m) <= 1 
     return m 
    // else list size is > 1, so split the list into two sublists 
    var list left, right 
    var integer middle = length(m)/2 
    for each x in m up to middle 
     add x to left 
    for each x in m after or equal middle 
     add x to right 
    // recursively call merge_sort() to further split each sublist 
    // until sublist size is 1 
    left = merge_sort(left) 
    right = merge_sort(right)

來源

2012-01-16 Luigi

感謝Reddy改進格式。 – Luigi 2012-01-16 10:48:22

這是一個算法問題而不是實現或語言問題，應該相應地標識/標記。 – 2012-01-16 11:30:14

Bottom-up merge sort是合併排序的非遞歸變體。

有關更詳細的僞代碼實現，另請參閱此wikipedia page。

來源

2012-01-16 10:47:17 unutbu

太棒了！感謝您的鏈接。 http://www.algorithmist.com非常有幫助。 – Luigi 2012-01-16 10:51:50

middle = len(lst)/2 
left = lst[:middle] 
right = lst[middle:]

列表切片工作正常。

來源

2012-01-16 10:47:58 TyrantWave

雖然遞歸嗎？ – Luigi 2012-01-16 10:56:39

啊，我以爲你在創建列表的左/右分割時意味着遞歸。對於實際排序的非遞歸，請使用unutbu提到的bottom-up。 – TyrantWave 2012-01-16 10:59:56

順便說一句 - 遞歸不是所不希望的本身。

如果您的堆棧空間有限，是否會發生遞歸（您是否害怕？;-)），或者在某些情況下函數調用的時間開銷非常令人擔憂。

大部分時間這些條件不成立;您的代碼的可讀性和可維護性將更加相關。在我看來，遞歸表示時，合併排序等算法更有意義。

來源

2012-01-16 12:14:50

我明白了。感謝您的洞察力。 – Luigi 2012-01-16 23:10:37

是否有將每個列表元素分隔到自己的列表中的非遞歸方式？

回答

相關問題