ruby的递归调用中的堆栈级别太深错误

Question

我正在尝试使用ruby实现快速排序算法。看看我做了什么：

class Array

  def quick_sort  #line 14
    less=[];greater=[]
    if self.length<=1
      self[0]
    else
      i=1
      while i<self.length
        if self[i]<=self[0]
          less << self[i]
        else
          greater << self[i]
        end
      i=i+1
      end
    end
    less.quick_sort + self[0] + greater.quick_sort #line 29
  end
end
[1,3,2,5,4].quick_sort #line 32

这就产生了错误：

bubble_sort.rb:29:in `quick_sort': stack level too deep (SystemStackError)
    from bubble_sort.rb:29:in `quick_sort'
    from bubble_sort.rb:32

为什么会发生这种情况？

Answer 1

我认为你的例子中的问题是你需要一个显式的return。

if self.length<=1
  self[0]

应该是

return [] if self == []

和

less.quick_sort + self[0] + greater.quick_sort #line 29

应该是

less.quick_sort + [self[0]] + greater.quick_sort #line 29

下面是一个有效的示例

class Array

  def quick_sort
    return [] if self == []
    pivotal = self.shift;
    less, greater = [], []
    self.each do |x|
      if x <= pivotal 
        less << x
      else 
        greater << x
      end
    end
    return less.quick_sort + [pivotal] + greater.quick_sort
  end
end
[1,3,2,5,4].quick_sort # => [1, 2, 3, 4, 5]

Answer 2

less.quick_sort + self[0] + greater.quick_sort

这一行在if语句之外，因此无论self.length<=1是否为true，它都会被执行。因此，该方法无限递归，这会导致堆栈溢出。

还应该指出的是，self[0]不返回数组(除非self是一个由数组组成的数组)，因此对它使用Array#+没有任何意义。它作为quick_sort方法的返回值也没有意义。

Answer 3

在这一部分中，您不应该处理"=“大小写。只应处理<和>。因此，您的算法永远不会停止并导致无限递归。

if self[i]<=self[0]
  less << self[i]
else
  greater << self[i]
end