堆棧使用合併排序

我試圖使用遞歸實現自己的合併排序。堆棧使用合併排序

def merge_sort(a,i,j) 
    if i < j 
    merge_sort(a,i,j/2) 
    merge_sort(a,j/2+1,j) 
    merge(a,i,j/2,j/2+1,j) 
    end 
end 

def merge(a,i,j,k,l) 
    # No implementation yet 
end

問題是我的執行結果在堆棧太深。我不應該得到這樣一個小陣列的這個錯誤消息。我試圖分類的數組只是五個元素。

b = [5,4,3,2,1] 
p merge_sort(b,0,b.size - 1) # => results in 'stack to deep' message

來源

2017-03-02 the_prole

第一步是調試。作爲第一行的'p [a，i，j]'可能會*非常明顯。我的錢正在一個錯誤的錯誤。 – tadman

下面是多數民衆贊成做多一點紅寶石般在如何更寬容的正確方向邁出的一步，再加上作爲獎金有實際的名稱，而不是數學速記：

def merge_sort(arr,from = nil,to = nil) 
    from ||= 0 
    to ||= arr.length 

    if (from < to) 
    part = from + (to - from)/2 

    merge_sort(arr, from, part) 
    merge_sort(arr, part + 1, to) 

    merge(arr, from,part, part+1, to) 
    end 
end 

def merge(a,from,j,k,l) 
    # No implementation yet 
end 

b = [5,4,3,2,1] 
merge_sort(b)

的錯誤來了關於從沒有正確定義分區點。在長度爲5的數組的原始代碼中，切點將爲2，並且當進一步劃分時，切點爲2/1或1，而不是2+（5-3）/ 2或3，因爲它應該是。從那裏開始，這一切都變得瘋狂了，因爲它是在錯誤地進行數學運算，並且不停地自稱無緣無故。

來源

2017-03-02 08:32:02 tadman

'＃沒有frommplementatfromon yet'有人試圖用Regexp解析Ruby？ ;-) –

是否有任何理由不使用'def merge_sort（arr，from = 0，to = arr.length）'？ –

@JörgWMittag這只是個人厭惡過度複雜的默認值。這當然是一種有效的方法。 – tadman

我的問題是我的中點公式是拋出遞歸到無限循環遞歸，直到堆棧溢出。代替

焦耳/ 2 + 1

它應該已經

（I + J）/ 2 + 1個

tadman得到了式右邊在他重新版本化

來源

2017-03-02 21:11:39

堆棧使用合併排序

回答

相關問題