Ocaml高效快速排序

Question

我想知道如何编写快速排序的高效版本其中列表分为一个通道。

我有这个代码片段，

let rec quicksort' = function 
[] -> [] 
| x::xs -> let small = List.filter (fun y -> y < x) xs 
      and large = List.filter (fun y -> y > x) xs 

in quicksort' small @ (x :: quicksort' large);; 

但在这里，我通过列表会超过1次（调用2次快速排序为小型和大型）。

的想法是做在只需一个步骤没有去列表1倍以上。

Answer 1

List.partition是要走的路：

let rec quicksort = function 
    | [] -> [] 
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs 
       in quicksort smaller @ (x::quicksort larger) 

注意List.partition有助于避免一个冗余穿越通过xs。您仍然需要递归排序较小部分和较大部分，因为它是Quicksort的工作方式。我不得不说quicksort这个版本远没有效率。 Quicksort algorithm是一种固有的原地算法，它递归地变换输入数组。另一个因素是枢轴选择;选择第一个元素作为支点并不总是一个好主意。

这些因素导致效率差异极大（可能使用Array和变异）。应使用List上的快速排序来演示该算法的思想及其递归之美。

Answer 2

如果您需要编写一个高效的排序功能，您可能需要阅读这篇有见地的论文：Engineering a sort function。否则，我很肯定List.sort也写得很好。