使用Ruby和Recursion的合并排序
当然，我正在实现这些算法: Coursera。我使用递归实现了合并排序，虽然排序正确，但我不确定它是否是该算法的正确实现。你们能看看吗？我怎样才能让它更“易读”呢？
##
# Implemetation of Merge Sort see: {https://pt.wikipedia.org/wiki/Merge_sort}
module Merge
class Sort
include Validator, Comparator
def sort(values)
return values if invalid_to_sort?(values)
_sort(values, 0, values.size - 1)
end
private
def _sort(values, ibegin, iend)
return [values[ibegin]] if ibegin == iend
mid = ((iend - ibegin) / 2) + ibegin
left = _sort(values, ibegin, mid)
right = _sort(values, mid + 1 , iend)
merge([], left, right)
end
def merge(values, left, right)
# p "values #{values} left #{left} right #{right}"
return values if left.empty? and right.empty?
if left.empty?
merge(values + [right.shift], left, right)
elsif right.empty? || (left.first <=> right.first) <= 0
merge(values + [left.shift], left, right)
else
merge(values + [right.shift], left, right)
end
end
end
end回答 1
Code Review用户
发布于 2015-10-02 09:53:23
是的，这两种方法似乎都正常工作，您的代码肯定实现了mergesort :)。
但是，您的代码看起来有点像C实现的直接翻译，因为它几乎不使用Ruby成语，这损害了可读性。Ruby数组知道它们的大小(#length、#empty?等)，所以您不需要跟踪它。因此，可以很好地拆分数组，如下所示：
# _sort now only accepts one argument, values
mid = values.length / 2
left = _sort(values[0...mid])当然，这种方法需要您重写#merge，但这是值得的，因为处理实际数组比处理严重的数字更容易阅读。这也可能消除了Validator模块存在的需要(而且Comparator似乎根本不被使用)。您应该始终致力于使用惯用的Ruby，因为代码的读者看到类似C的东西会浪费大量时间思考“为什么<插入idiom>不够吗？”来分析你的代码。
如果有人将wierd值传递给您的#sort (例如，Fixnum)，它将引发类似于NoMethodError: undefined method 'empty?'的神秘错误。您应该通过拯救这些错误并提出更多描述性错误(在本例中，可能是ArgumentError )来处理这些错误，这样它们就更容易分析了。#merge应该单独处理，因为NoMethodError可能意味着其他的东西。
def invalid_to_sort?(values)
# I don't think nil deserves special treatment here though, it should
# raise ArgumentError like all non-arrays. This seems to come from
# C where arrays are pointers and NULL is pointer too, so they are
# hard to distinguish without direct check
values.nil? || values.empty? || values.one?
rescue NoMethodError
raise ArgumentError, "some descriptive message"
end您当前的代码结构引入了一些奇怪的(非Ruby)接口。
sorter = Merge::Sort.new
sorted = sorter.sort(array)下面是标准库的示例，Rubyish要做的事情如下：
array.merge_sort! # destructive
# and
sorted = array.merge_sort # safe通过对重复进行安全的变体工作，可以很容易地做到这一点：
class Array
def merge_sort!
# ... code code code ...
end
def merge_sort
dup.merge_sort!
end
end当然，修补标准类是危险的，但正如各种例子(尤其是Rails)所证明的那样，也是非常有用的。如果您担心，您可以使用精练，但这些都是实验性的。但是，由于您正在添加新功能(而不是替换现有功能)，只有真正的危险与其他修补程序冲突，所以我想说的是去做吧。
在任何情况下，都不需要引入类，更需要实例化的类。如果您想要外部排序方法(以避免修补Array)，只需将其作为模块的一部分，以保持简单，即：
module Sort
def self.merge_sort(values)
# ... code code code ...
end
end
sorted = Sort.merge_sort(array)现在，我从前面的问题中了解到，您来自Java，所以您喜欢实例化大量;)但是在Ruby中，我们的工作方式有些不同，在这里，模块/类是一个正常的对象，它可以像其他任何东西一样工作，而不是某种元数据，所以很容易使用依赖项注入，而且通常不需要仅仅为了调用一些代码而创建实例:)
https://codereview.stackexchange.com/questions/106254
复制相似问题
腾讯云开发者
