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

Question

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

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]

但是它打印出来:

5
2

4
6

1
7

3
8

它是如何工作的？

Answer 1

你至少有两个问题。

首先，else声明没有效果，这不是你怎么做if else在 Ruby 中。

其次，如果a.length < 2是false那么你的方法将返回 nil . puts返回 nil , x = nil返回 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 =