这是我的快速排序实现list-based
:
let partition pivot l =
let rec p left right = function
| [] -> (left, right)
| hd::tl ->
let c = compare pivot hd
in
if c > 0 then
p (hd::left) right tl
else
p left (hd::right) tl
in
p [] [] l;;
let quicksort l =
let rec qs = function
| [] -> []
| pivot::tl ->
let (left, right) = partition pivot tl
in
(qs left) @ (pivot::(qs right))
in
qs l;;
当我尝试使用 列表时100,000
,它很好并且没有问题。
但是,如果我尝试使用1,000,000
,它会给出错误stack_overflow
。
我不明白为什么它会给出stack_overflow
,因为我认为堆栈大小应该是这样的log1000000 ~ 20
,对吧?