Ruby中的遞歸合併排序

Question

我想寫一個遞歸執行合併排序的ruby方法。我有方法的工作，但這是我不小心得到它的工作，所以我不知道爲什麼它的工作原理，並希望瞭解我寫的代碼是如何工作的。在psuedocode中，我遵循的步驟如下所示。

1. 分割長度爲n的原始數組，直到我有長度爲1
2. 合併的n個陣列和在時間排序2陣列的長度m可返回長度爲m * 2
3. 重複上述步驟的陣列直到我有一個現在排序的長度數組

基本上這對我來說是一個大樹分支到n個分支，每個分支包含一個長度爲1的數組。然後我需要把這些n分支，並以某種方式將它們合併回到方法內的單個分支中。

def merge_sort(arr) 
    return arr if arr.length == 1 
    merge(merge_sort(arr.slice(0, arr.length/2)), 
     merge_sort(arr.slice(arr.length/2, arr[-1]))) 
end 

def merge(arr1, arr2) 
    sorted = [] 
    begin 
    less_than = arr1[0] <=> arr2[0] 
    less_than = (arr1[0] == nil ? 1 : -1) if less_than == nil 
    case less_than 
    when -1 
     sorted << arr1[0] 
     arr1 = arr1.drop(1) 
    when 0 
     sorted << arr1[0] 
     sorted << arr2[0] 
     arr1 = arr1.drop(1) 
     arr2 = arr2.drop(1) 
    when 1 
     sorted << arr2[0] 
     arr2 = arr2.drop(1) 
    end 
    end until (arr1.length == 0 && arr2.length == 0) 
    sorted 
end 

merge_sort([1,6,3,8,22,3,11,24,54,68,79,80,98,65,46,76,53]) 

#Returns => [1, 3, 3, 6, 8, 11, 22, 24, 46, 53, 54, 65, 68, 76, 79, 80, 98] 

我其實正確的方法對列表進行排序，但我不能完全確定該方法如何結合每個分支，然後返回排序合併列表，而不是它結合只是前兩個長一個數組。

此外，如果任何人有我怎樣才能使合併方法漂亮看起來更像我已成長爲愛，請讓我知道Ruby代碼的想法。

Answer 1

這是我在Ruby中

def mergesort(array) 
    return array if array.length == 1 
    middle = array.length/2 
    merge mergesort(array[0...middle]), mergesort(array[middle..-1]) 
end 


def merge(left, right) 
    result = [] 
    until left.length == 0 || right.length == 0 do 
    result << (left.first <= right.first ? left.shift : right.shift) 
    end 
    result + left + right 
end 

實施歸併的正如你所看到的，mergesort方法基本和你一樣，而這正是遞歸發生，這樣是什麼，我會重點關注。

首先，你有你的基本情況：return array if array.length == 1這是允許遞歸的工作，而不是無限期地繼續下去。

接下來，我在執行我所定義的變量middle代表陣列的中間：middle = array.length/2

最後，第三行是所有的工作情況：merge mergesort(array[0...middle]), mergesort(array[middle..-1])

什麼，你在這裏做告訴合併方法合併左半部分和合並右半部分。

如果假設你輸入數組是[9, 1, 5, 4]你說的話是merge mergesort([9, 1]), mergesort([5, 4])。

爲了執行合併，首先必須歸併[9,1]和歸併[5,4]。遞歸就變成

merge((merge mergesort([9]), mergesort([1])), (merge mergesort([5]), mergesort([4]))) 

當我們再次遞歸的mergesort([9])已經達到了基本情況，並返回[9]。同樣，mergesort([1])也已達到基本情況並返回[1]。現在你可以合併[9]和[1]。合併的結果是[1, 9]。

現在爲合併的另一方。在我們可以將它與[1, 9]合併之前，我們必須弄清merge mergesort([5]), mergesort([4])的結果。遵循與左側相同的程序，我們得到[5]和[4]的基本情況併合並那些得到[4, 5]。我們需要合併[1, 9]與[4, 5]。

1. 在第一遍，result接收1因爲1 < = 4
2. 在下通，我們正在與result = [1]，left = [9]，和right = [4, 5]工作。當我們看到left.first <= right.first時，我們發現它是錯誤的，所以我們返回right.shift或4。現在result = [1, 4]。
3. 在第三階段，我們正在與result = [1, 4],left = [9]和right = [5]合作。當我們看到left.first <= right.first時，我們發現它是錯誤的，所以我們返回right.shift或5。現在result = [1, 4, 5]。
4. 循環結束，因爲right.length == 0。
5. 我們簡單地連接result + left + right或[1, 4, 5] + [9] + []，這會導致排序的數組。