0

下面是我在 ruby​​ 中的快速排序实现（使用第一个元素作为枢轴）。但是有一个错误我不知道为什么

def quicksort(items)
   return items if items.nil? or items.length <= 1

   first=items[0]

   left,right=parti(items,0,items.length)

   quicksort(left) + [first] + quicksort(right)

end

def parti(s,l,r)
  p=s[l]
  i=l+1
  (l+1..r).each do |x|
      if s[x] < p
          s[x],s[i] = s[i],s[x]
          i+=1
      end
  end
  s[l],s[i-1] = s[i-1],s[l]
  return [s[0..i-2],s[i..r]]
end

错误：

putarray.rb:38:in `block in parti': undefined method `<' for nil:NilClass (NoM
hodError)
      from inputarray.rb:37:in `each'
      from inputarray.rb:37:in `parti'
      from inputarray.rb:22:in `quicksort'
      from inputarray.rb:47:in `<main>'

它说

 if s[x] < p

s[x] 是 NilClass。

更新：事实证明 

left,right=parti(items,0,items.length) should be 
left,right=parti(items,0,items.length-1)

但是在这个改变之后，一个错误

inputarray.rb:37: stack level too deep (SystemStackError)

指向

(l+1..r).each do |x|

在互联网上没有找到任何好的解释。

4

1 回答 1

1

请记住，在 Ruby 中，数组索引从 0 开始，而不是 1。

因此items.length将返回大于数组中最大索引的值 1。

尝试right=parti(items,0,items.length-1)代替right=parti(items,0,items.length).

于 2012-06-28T21:30:03.570 回答