7

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

我有这段代码，

    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 次。

4

2 回答 2

20

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效率还差得很远。快速排序算法是一种固有的就地算法，它递归地改变输入数组。另一个因素是支点选择。选择第一个元素作为枢轴并不总是一个好主意。

这些因素导致效率的实现截然不同（可能使用Array和变异）。应该List使用快速排序来展示算法的思想及其递归的美妙之处。

于 2012-05-15T11:06:44.967 回答
4

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

于 2012-05-18T20:46:24.570 回答