小编aja*_*jay的帖子

我是Ruby的新手,几天前就开始学习语言了.作为练习,我尝试实现一个简单的快速排序

class Sort
  def swap(i,j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def quicksort(lower=0, upper = @data.length - 1)
    return nil if lower >= upper
    m = lower
    i = 0
    ((lower+1)..upper).each do |i|
      swap(++m, i) if @data[i] < @data[lower]
    end

    swap(m, lower)

    quicksort1(lower, m -1)
    quicksort1(m+1, upper)
  end
end

在10000个整数上调用quicksort会给出堆栈级错误.在谷歌上搜索之后,我发现Ruby中没有支持尾递归(有点).但后来我找到了以下代码片段(从这里开始)

def qs(v)
  return v if v.nil? or v.length <= 1
  less, more = v[1..-1].partition { |i| i < v[0] }
  qs(less) + [v[0]] + qs(more)
end …