Ruby中的递归合并排序

Question

我正在尝试编写一个ruby方法，它可以递归地执行合并排序。我有这个方法，但这是一次我偶然得到它的工作，所以我不知道它为什么工作，并很想了解我写的代码是如何工作的。在psuedocode中，我遵循的步骤如下所示。

1. 拆分长度为n的原始数组，直到我拥有长度为1的n个数组
2. 一次合并和排序长度为m的2个数组，以返回长度为m*2的数组
3. 重复上述步骤，直到我有一个长度为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]

我所拥有的方法实际上正确地排序了列表，但我不完全确定该方法是如何组合每个分支然后返回排序的合并列表的，而不是仅仅返回它组合的前两个数组。

此外，如果有人对我如何使merge方法看起来更像我所喜爱的ruby代码有想法，请告诉我。

Answer 1

下面是我的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]

Answer 2

下面是我在Ruby中实现的mergesort

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方法与您的方法基本相同，这是递归发生的地方，因此我将重点介绍这一点。

首先，您有基本情况:如果array.length==1这是允许递归工作而不是无限期地继续下去的原因。

接下来，在我的实现中，我定义了一个变量middle来表示数组的中间:middle=array.length/2

最后，第三行是所有工作发生的地方:merge mergesort(array[0...medide]),mergesort(array[medide..-1])

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

如果假设输入数组是[9,1,5,4]，那么您要说的是merge mergesort([9,1]),mergesort([5,4])。

为了执行合并，首先必须进行mergesort[9,1]和mergesort[5,4]。然后递归变成

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

当我们再次递归时，mergeSort([9])已到达基本大小写并返回[9]。类似地，mergeSort([1])也已到达基本大小写，并返回[1]。现在可以合并[9]和[1]。合并的结果为[1,9]。

现在是合并的另一边。我们必须计算出合并mergesort([5])、mergesort([4])的结果，然后才能将其与[1,9]合并。按照与左侧相同的过程，我们得到[5]和[4]的基本情况，并将它们合并得到[4,5]。

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

1. 在第一次传递时，result接收1，因为1<=4。
2. 在下一个pass中，我们使用result=[1]、left=[9]和right=[4,5]。当我们看到left.first<=right.first是否为false，因此返回right.shift或4。现在结果=[1,4]。
3. 在第三遍中，我们使用result=[1,4]、left=[9]和right=[5]。当我们看到left.first<=right.first是否为false，因此返回right.shift或5。现在结果=[1,4,5]。
4. 在此循环结束，因为正确。length==0。
5. 我们简单地将result+left+right或[1,4,5]+[9]+[]串联起来，从而得到一个排序数组。