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] + []，这会导致排序的数组。