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次快速排序).

我们的想法是只需一步即可完成,而无需多次访问列表.

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算法是一种固有的就地算法,它递归地改变输入数组.另一个因素是枢轴选择; 选择第一个元素作为枢轴并不总是一个好主意.

这些因素导致效率的极端不同(可能使用Array和变异).Quicksort on List应该用于演示算法的思想和递归的美感.