使用递归的归并排序算法

Merge sort algorithm using recursion

我在做奥丁计划。练习题是:使用递归创建归并排序算法。以下是根据某人的解决方案修改的:

def merge_sort(arry)
  # kick out the odds or kick out of the recursive splitting?
  # I wasn't able to get the recombination to work within the same method.
  return arry if arry.length == 1
  arry1 = merge_sort(arry[0...arry.length/2])
  arry2 = merge_sort(arry[arry.length/2..-1])
  f_arry = []
  index1 = 0 # placekeeper for iterating through arry1
  index2 = 0 # placekeeper for iterating through arry2
  # stops when f_arry is as long as combined subarrays
  while f_arry.length < (arry1.length + arry2.length)
    if index1 == arry1.length
      # pushes remainder of arry2 to f_arry
      # not sure why it needs to be flatten(ed)!
      (f_arry << arry2[index2..-1]).flatten!
    elsif index2 == arry2.length
      (f_arry << arry1[index1..-1]).flatten!
    elsif arry1[index1] <= arry2[index2]
      f_arry << arry1[index1]
      index1 += 1
    else
      f_arry << arry2 [index2]
      index2 += 1
    end
  end
  return f_arry
end
  1. 第一行return arry if arry.length == 1是否将其踢出数组的递归拆分,然后绕过方法的递归拆分部分回到重组部分?似乎它应该在它递归通过时返回到该部分后继续重新拆分它。

  2. 为什么一定要 flatten-ed?

理解第一行的最简单方法是理解 merge_sort 绑定的唯一契约是 "return a sorted array" - 如果数组只有一个元素 (arry.length == 1 ) 它 已经排序 - 所以不需要做任何事情!只需 return 数组本身。

在递归中,这称为 "Stop condition"。如果您不提供停止条件 - 递归将永远不会结束(因为它总是会调用自己 - 而且永远不会 return)!

你需要 flatten 结果的结果,是因为你将数组作为元素推送到结果数组中:

arr = [1]
arr << [2, 3]
# => [1, [2, 3]]

如果您尝试仅在迭代结束时展平生成的数组,而不是在添加元素时展平,则会出现问题,因为它的 length会偏斜:

arr = [1, [2, 3]]
arr.length
# => 2

虽然 arr 包含三个 数字 它只有 两个元素 - 这会破坏你的解决方案。

您希望数组中的所有元素都是数字,而不是数组。 flatten! 确保数组中的所有元素都是原子,如果不是,它会将子数组的元素添加到自身而不是子数组:

arr.flatten!
# => [1, 2, 3]

您可能要考虑的另一个选项(并且会更有效)是使用 concat 代替:

arr = [1]
arr.concat([2, 3])
# => [1, 2, 3]

此方法将作为参数传递的数组中的所有元素添加到调用它的数组中。