1

我quicksort在 OCaml 中实现。这是代码：

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond;;

let partition = function
  | [] -> ([], [], [])
  | pivot::tl ->
    let rec p (left, right) = function
      | [] -> (left, right, [pivot])
      | first::rest ->
    let c = compare pivot first
    in 
    if c > 0 then
      p (first::left, right) rest
    else 
      p (left, first::right) rest
    in
    p ([], []) tl;;

let quicksort l =
  let sl = shuffle l 
  in
  let rec qs = function
    | [] -> []
    | l ->
      let (left, right, pivot) = partition l
      in 
      (qs left) @ pivot @ (qs right)
  in 
  qs sl;;

首先，我认为也许有更好的方法来实现分区。List.partition我想到了，但我只是想自己实现关键部分

其次，我@在排序中使用了很多，inefficient对吧？

有什么建议么？

编辑

另一个需要考虑的问题是是否3-way quicksort会影响 OCaml 中的实现？

4

2 回答 2

2

p函数缩进严重；说到缩进，我倾向于认为in在下一行有 a 的风格对于单行声明来说太过分了，所以我宁愿把它们放在单行声明的末尾。

更重要的是，它不需要将列表元组作为参数，使用两个单独的（咖喱）参数，您将在语法上更轻松。您还可以使用List.partition标准库的功能。

于 2013-02-26T21:49:42.067 回答
2

您可以尝试的微优化是 List.concat[[qs left]; [pivot]; [qs right]]一次附加列表，但您需要运行一些基准测试来验证这是否有帮助。

于 2013-02-26T21:58:58.393 回答