Ruby 中的递归归并排序

Question

我正在尝试编写一个 ruby 递归执行合并排序的方法。我有这个方法，但这是我不小心让它工作的时候之一，所以我不知道它为什么有效，并且很想了解我编写的代码是如何工作的。在伪代码中，我遵循的步骤如下所示。

拆分长度为n的原始数组，直到我有n个长度为1的数组
一次将2个长度为m的数组合并排序为return一个长度为m*2的数组
重复上述步骤，直到我得到一个长度为 n

基本上这在我看来是一棵分支成 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]

我的方法实际上对列表进行了正确排序，但我不完全确定该方法如何组合每个分支然后 returns 排序后的合并列表，而不仅仅是前两个长度的数组合并.

此外，如果有人对我如何使合并方法更漂亮以使其看起来更像我逐渐喜欢的 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])

您在这里所做的是告诉 merge 方法将已合并排序的左半部分与已合并排序的右半部分合并。

如果你假设你的输入数组是 [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]) 已经达到基本情况并且 returns [9]。同样，mergesort([1])也达到了基本情况，returns[1]。现在您可以合并 [9] 和 [1]。合并的结果是[1, 9].

现在是合并的另一端。我们必须先弄清楚 merge mergesort([5]), mergesort([4]) 的结果，然后才能将其与 [1, 9] 合并。按照与左侧相同的步骤，我们得到 [5] 和 [4] 的基本情况并将它们合并以获得 [4, 5].

现在我们需要将 [1, 9] 与 [4, 5] 合并。

在第一遍中，result 收到 1 因为 1 <= 4.
在下一轮中，我们将使用 result = [1]、left = [9] 和 right = [4, 5]。当我们看到如果 left.first <= right.first 我们看到它是假的，所以我们 return right.shift，或者 4。现在result = [1, 4].
在第三遍中，我们正在处理 result = [1, 4]、left = [9] 和 right = [5]。当我们看到如果 left.first <= right.first 我们看到它是假的，所以我们 return right.shift，或者 5。现在 result = [1, 4, 5].
这里循环结束，因为right.length == 0.
我们简单地连接 result + left + right 或 [1, 4, 5] + [9] + []，从而得到一个排序数组。

Answer 2

这是我的 Ruby 递归 merge_sort 方法版本。与上面完全相同，但略有不同。

    def merge_sort(array)
        array.length <= 1 ? array : merge_helper(merge_sort(array[0...array.length / 2]), merge_sort(array[array.length / 2..-1]))
    end


    def merge_helper(left, right, merged = [])
        left.first <= right.first ? merged << left.shift : merged << right.shift until left.length < 1 || right.length < 1 
        merged + left + right
    end


p merge_sort([]) # => []
p merge_sort([20, 8]) # => [8, 20]
p merge_sort([16, 14, 11]) # => [11, 14, 16]
p merge_sort([18, 4, 7, 19, 17]) # => [4, 7, 17, 18, 19]
p merge_sort([10, 12, 15, 13, 16, 7, 19, 2]) # => [2, 7, 10, 12, 13, 15, 16, 19]
p merge_sort([3, 14, 10, 8, 11, 7, 18, 17, 2, 5, 9, 20, 19]) # => [2, 3, 5, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20]

Ruby 中的递归归并排序

Recursive merge sort in Ruby

ruby

sorting

recursion

mergesort