新手问题 写了一个快排算法,总是报错:stack level too deep (SystemStackError)

kww · 2014年07月03日 · 最后由 yfractal 回复于 2014年07月06日 · 3119 次阅读
def quick_sort(list)
    return list if list.size <= 1
    p = list.sample
    left, right = list.partition{|elmt| elmt <= p}
    quick_sort(left) + quick_sort(right)
end

a = [9,8,7,6,5,0,6]
b = quick_sort(a)
puts b

我真没看出有何问题。但是却报错:4: stack level too deep (SystemStackError) 第四行left, right = list.partition{|elmt| elmt <= p}有何问题?

多谢!

当你的的 list 被切到 [6, 6] 的时候 partion 出来的还是 [6, 6] 就这么死循环下去了

#1 楼 @leozwa 多谢。看来上面算法只适用于无重复的序列。

#2 楼 @kww 你稍微改一下,把选出来的 pivot 隔离出来,别把的 pivot 也传下去就好了 最后quick_sort(left) + [pivot] + quick_sort(right)

#3 楼 @leozwa 明白你的思路了,但不知怎样隔离选出来的 pivot。

#4 楼 @kww 简单点的方法 把 pivot 和 list[0] 交换 做 partition 的时候从 list[1] 开始

#5 楼 @leozwa 把第三行改成这样貌似就可以了return list if list.size <= 1 or list.uniq.size == 1

#4 楼 @kww

def q_sort(array)
  return array if array.length < 2
  pivot = array.pop
  less, more = array.partition { |i| i < pivot }
  q_sort(less) + [pivot] + q_sort(more)
end

#7 楼 @loveltyoic 谢谢。总觉得固定末尾取 pivot 不如随机的快点,当然是在概率意义下。

@kww 一般不都是用三数中值(左端,右端,中心位置的中间值)来作为 pivot 吗

#8 楼 @kww 之所以选择随机的 pivot 只是为了避免 O(n^2) 的最差复杂度,对于一般的序列,选择固定的 pivot 反而要快一些,毕竟 rand 也是需要时间的。

不过,这个算法最复杂的地方就在于 partition 啊,应该着重实现 partition 的部分才对

#10 楼 @Alexander OK, I see. Thanks!

在都的机器上,list.sample 一直是一个值

#13 楼 @yfractal 不会吧:

1.9.3p448 :001 > a = [1,2,3,4,5,6]
 => [1, 2, 3, 4, 5, 6] 
1.9.3p448 :002 > a.sample
 => 4 
1.9.3p448 :003 > a.sample
 => 2 
1.9.3p448 :004 > a.sample
 => 4 
1.9.3p448 :005 > a.sample
 => 4 
1.9.3p448 :006 > a.sample
 => 3 
1.9.3p448 :007 > a.sample
 => 3 
1.9.3p448 :008 > 

不知道你的根据是什么?

直接在p = list.sample 下面加的 puts p

def quick_sort(list)
    return list if list.size <= 1
    p = list.sample
    puts p
    left, right = list.partition{|elmt| elmt <= p}
    quick_sort(left) + quick_sort(right)
end

ruby 2.0.0p247

需要 登录 后方可回复, 如果你还没有账号请 注册新账号