ruby - Ruby 不可能进行高速排序吗？

Question

我研究了这本深刻的指南，它确实帮助我掌握了语言挺快的。之后，我开始解决一些编码难题使用 ruby 。习惯我的感觉对我有很大帮助。

我被一个这样的谜题困住了。我很容易解决它，因为它是非常简单，但解决方案被拒绝(由主机网站)错误“超时”!我知道 Ruby 无法竞争以 C/C++ 的速度，但它必须能够在接受的网站上回答一个小谜题Ruby 中的解决方案？

puzzle只是一个普通的排序。

这是我的解决方案

array ||= []
gets.to_i.times do
  array << gets
end
puts array.sort

我的问题是，有没有其他方法可以用 Ruby 实现高速排序？我在这里使用基本的 Array#sort，但有没有办法更快地完成它，即使这意味着更多的代码行？

Answer 1

我已经解决了这个问题，让我告诉您使用 nlogn 算法几乎是不可能通过的，除非您使用它的非常优化的 C/Assembly 版本。

您需要探索其他算法。 提示:O(n) 算法可以解决问题，即使对于 ruby​​。

祝你好运。