Ruby中的递归合并排序

Question

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

1. 拆分长度为n的原始数组,直到我有n个长度为1的数组
2. 合并并对2个长度为m的数组进行排序,以返回长度为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]

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

此外,如果有人有关于我如何使合并方法更漂亮,看起来更像我喜欢的红宝石代码的想法,请让我知道.

Answer 1

这是我在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方法与您的方法基本相同,这是递归发生的地方,这是我将关注的内容.

首先,你有你的基本情况:return array if array.length == 1 这是允许递归工作而不是无限期继续下去的原因.

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

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

你在这里做的是告诉merge方法将mergesorted左半部分与mergesorted右半部分合并.

如果你假设你的输入数组是[9, 1, 5, 4]你所说的merge mergesort([9, 1]), mergesort([5, 4]).

为了执行合并,首先必须合并[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].

现在为合并的另一边.merge mergesort([5]), mergesort([4])在我们将它合并之前,我们必须弄清楚结果[1, 9].按照与左侧相同的步骤,我们得到了基本情况[5]和[4]并合并得到的[4, 5].

现在,我们需要合并[1, 9]使用[4, 5].

1. 在第一次传递时,因为1 <= 4而result接收1.
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] + []导致排序数组.