Ruby 合并排序 -- 这个递归函数是如何工作的？

Question

我正在做一项作业，在 Ruby 中编写递归归并排序算法。我试图将其逐个分解，以便能够围绕它进行思考。到目前为止，我正在尝试完成 "divide" 步骤，直到每个数组中只剩下一个元素。

a = [5, 2, 4, 6, 1, 7, 3, 8]

def divide(arr)
  return arr if arr.length < 2
    else
      arr1 = puts divide(arr[0..arr.length/2-1])
      arr2 = puts divide(arr[arr.length/2..arr.length])
end

我认为输出将是：

[5] [8]

但它打印出来：

它是如何工作的？

Answer 1

你至少有两个问题。

首先，else语句没有效果，不是你在Ruby中if else的做法。

其次，如果 a.length < 2 是 false 那么您的方法将 return nil。 puts returns nil, x = nil returns nil.

我添加了一些打印件来演示您的代码是如何工作的，希望对您有所帮助：

$level = 0

def divide(arr)
  return arr if arr.length < 2

  $level += 1

  puts "Working with array #{arr}"

  arr1 = divide(arr[0..arr.length/2-1])
  puts "Level = #{$level} arr1 = #{arr1}"
  arr2 = divide(arr[arr.length/2..arr.length])
  puts "Level = #{$level} arr2 = #{arr2}"

  $level -= 1

  nil
end

divide([5, 2, 4, 6, 1, 7, 3, 8])

输出：

Working with array [5, 2, 4, 6, 1, 7, 3, 8]
Working with array [5, 2, 4, 6]
Working with array [5, 2]
Level = 3 arr1 = [5]
Level = 3 arr2 = [2]
Level = 3 arr1 = 
Working with array [4, 6]
Level = 4 arr1 = [4]
Level = 4 arr2 = [6]
Level = 4 arr2 = 
Level = 4 arr1 = 
Working with array [1, 7, 3, 8]
Working with array [1, 7]
Level = 6 arr1 = [1]
Level = 6 arr2 = [7]
Level = 6 arr1 = 
Working with array [3, 8]
Level = 7 arr1 = [3]
Level = 7 arr2 = [8]
Level = 7 arr2 = 
Level = 7 arr2 =

Ruby 合并排序 -- 这个递归函数是如何工作的？

Ruby merge sort -- how does this recursive function work?

ruby

arrays

algorithm

recursion

mergesort