快速排序实现：栈级别太深（SystemStackError）

Question

我正在尝试在Ruby中实现快速排序，但是出现了错误`quicksort'：堆栈层数太深（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，看起来它可以工作。

- lesce

---

快速排序算法在病态情况下使用的堆栈层数最多可以达到n级，其中n是输入元素的数量。当遇到这种情况时，只有增加堆栈大小、选择更好的中轴方法（可以减少病态案例），或更改快速排序实现才能解决它。如果发生在小n的情况下，那么终止条件当然是错误的 :) 什么是导致此异常的[最小]输入？ - user166390

你在什么情况下遇到了这个错误？ - Ryanmt

我将 else => elsif x > pivot 进行了修改，现在看起来可以工作了。 - lesce

Answer 1

你的算法对我有用，即使在我生成一个测试用数组时，其长度达到1e7。

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

虽然完成这个任务需要约4.5 GB的内存，但是输出结果的清理工作也同样重要...

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] 

- Ryanmt

Answer 2

您需要从数组中删除枢轴，因为您稍后会将其添加回去。因此，不要这样做：

pivot = array[array.length/2]

你应该已经完成了。

pivot = array.delete_at(array.length/2)

- kentor

Answer 3

在 Ruby 中，默认情况下堆栈大小设置得相当小。因此，使用大型数据集进行递归函数时很容易爆栈。

确保不会无限递归的最简单方法是在非常小的数据集上运行快速排序。如果它仍然崩溃，那么你就知道你正在无限递归。

你可以在 这篇文章 中找到 Matz 回复的一些关于堆栈大小的信息。

- Dty

---

但是在快速排序中，堆栈大小应该保持非常小，除非实现在已排序的数据上崩溃。即使数组填满了所有内存，堆栈大小也将约为lg(n) - 远远小于任何脚本语言的限制！ - japreiss

Answer 4

你的函数正在无限递归。使用ruby-debug来找出原因。

编辑1：

我认为你想让函数的最后一行是这样的：

return quicksort(less) + quicksort(greater)

- David Grayson