arrays - 在没有内置 ruby​​ 函数的情况下合并两个排序数组

Question

我试图在不使用任何内置排序方法的情况下合并两个排序数组。这是我目前所拥有的。

def merge(array_1, array_2)
    i = 0
    k = 0
    merged_array = []
    while i < array_1.count && k < array_2.count
        while k < array_2.count && array_1[i] > array_2[k]
            merged_array << array_2[k]
            k += 1
        end
        merged_array << array_1[i]
        i += 1
    end
    merged_array
end

array_1 = [5,8,9,11]
array_2 = [4,6,7,12,13]

p merge(array_1, array_2)

输入是 array_1 = [5,8,9,11] 和 array_2 = [4,6,7,12,13] 假设输出为 [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]。有人可以解释为什么它不起作用。谢谢!

Answer 1

试试这个

def merge(array_1, array_2)
  return enum_for(__method__, array_1, array_2) unless block_given?

  a = array_1.each
  b = array_2.each
  loop { yield a.peek < b.peek ? a.next : b.next }

  # Your code is not working because the equivalent of these two lines
  # is missing. After you reach the end of one array you have to append
  # all remaining elements of the other array. I am doing this here by
  # just exhausting both enumerators, one of which is empty by now.

  loop { yield a.next }
  loop { yield b.next }
end

p merge([5, 8, 9, 11], [4, 6, 7, 12, 13]).entries

无需跟踪索引。合并排序可以追溯到大型机和磁带时代，因此可以仅使用枚举器来实现。

这是如何工作的？

• each 创建枚举数
• peek 返回下一个元素而不推进枚举数
• next 返回枚举器前进的下一个元素
• 以上两个都在到达枚举器末尾时引发StopIteration
• loop 重复一段代码，直到引发 StopIteration