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 回答