F#中最优雅的冒泡方法是什么？

Question

F#中最优雅的冒泡方法是什么？

UPDATE

正如其中一个答案所指出的那样,泡泡排序在函数式语言中并不高效.一个幽默愤世嫉俗的评论者也指出,只有当列表很小并且几乎无论如何都要排序时,泡泡分类才适用.

但是,我很想知道如何在F#中编写一个聪明的冒泡,因为我过去在C#,C++和Java EE中做过泡泡排序,因为我是F#newbie.

Answer 1

在函数式语言中使用冒泡排序效率不高,因为实现必须多次反转列表(对于不可变列表,这不能真正有效地实现).

无论如何,Erlang的例子可以像这样重写为F#:

let sort l = 
  let rec sortUtil acc rev l =
    match l, rev with
    | [], true -> acc |> List.rev
    | [], false -> acc |> List.rev |> sortUtil [] true
    | x::y::tl, _ when x > y -> sortUtil (y::acc) false (x::tl)
    | hd::tl, _ -> sortUtil (hd::acc) rev tl
  sortUtil [] true l

另一方面,您可以使用可变数组实现相同的算法.这将更有效,在F#中,如果需要,您也可以使用数组.以下函数创建数组的副本并对其进行排序.

let sort (arr:'a[]) = 
  let arr = arr |> Array.copy
  let swap i j = let tmp = arr.[i] in arr.[i] <- arr.[j]; arr.[j] <- tmp
  for i = arr.Length - 1 downto 0 do
    for j = 1 to i do
      if (arr.[j - 1] > arr.[j]) then swap (j-1) j
  arr

托马斯