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

Question

我研究了这本尖锐的指南,它确实帮助我快速掌握了这门语言.之后,我开始使用Ruby解决一些编码难题.它很有助于习惯我所感受的语言.

我遇到了一个这样的谜题.我很容易解决它,因为它非常直接,但解决方案被主机网站拒绝,错误是"时间超过"!我知道Ruby无法与C/C++的速度竞争,但它必须能够在一个接受Ruby解决方案的网站上回答一个小小的难题吗？

这个谜题只是一种正常的方式.

这是我的解决方案

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

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

Answer 1

我已经解决了这个问题,让我告诉你使用nlogn算法传递这几乎是不可能的,除非你使用的是非常优化的C /汇编版本.

您需要探索其他算法.提示:即使对于ruby,O(n)算法也能解决问题.

祝好运.