当你的的 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