0

这是我的快速排序实现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，对吧？

4

3 回答 3

5

@我假设操作员将使用线性数量的堆栈。（这只是对列表进行快速排序的问题之一。）

这是@Pervasives 模块的定义：

let rec ( @ ) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

就目前而言，这是一种异常缓慢的排序。如果你真的想让这个工作，你必须更聪明。至少你需要一个尾递归版本的@.

于 2013-03-04T18:01:38.133 回答
1

快速排序不能用于链表。效果不好。用于列表的正确排序算法是归并排序。基本上，一旦你在算法中使用列表连接，你就应该意识到你没有做对，或者你应该使用其他数据结构。列表有很多优点，串联不是其中之一。

于 2013-03-05T19:26:33.760 回答
0

如前所述，问题在于@。这不是一个无法解决的问题：您需要将内部排序函数重新定义为排序和连接的函数。

 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 l acc = 
   match l with
     | [] -> acc
     | pivot::tl ->
       let (left, right) = partition pivot tl
       in 
       qs left (pivot::(qs right acc)) 
   in 
   qs l [];;
于 2013-03-15T06:05:13.360 回答