ruby - 快速排序实现 : stack level too deep (SystemStackError)

Question

所以我试图在 ruby​​ 中实现快速排序，但我得到了这个错误 `quicksort': stack level too deep (SystemStackError)

def quicksort(array)
  if array.length <= 1
    return array
  end
  less = Array.new
  greater = Array.new
  pivot = array[array.length/2]
  array.each do |x|
    if x < pivot
      less << x
    else 
      greater << x
    end
  end
  return quicksort(less) << pivot << quicksort(greater)
end

编辑 我将 else 更改为 elsif x > pivot 并且它似乎有效。

Answer 1

你的算法对我有用，当我生成一个数组进行测试时甚至达到 1e7。

 quicksort Range.new(1,1e7).to_a.shuffle

当然，这需要大约 4.5 GB 的 RAM 才能完成。至于清理输出......

ruby-1.9.3-p0 :018 >       quicksort [1,3,2] # => [1, 2, [], 3, []] 
ruby-1.9.3-p0 :019 >     quicksort [1,4,2,3] # => [1, 2, [3, [4]]] 

改变这一行:

  return (quicksort(less) << pivot << quicksort(greater)).flatten.compact

它使一切变得更干净。

ruby-1.9.3-p0 :037 >       quicksort [1,3,2] # => [1, 2, 3] 
ruby-1.9.3-p0 :038 >     quicksort [1,4,2,3] # => [1, 2, 3, 4]