F# 中最优雅的冒泡排序方式是什么?
UPDATE
正如其中一个答案所指出的,冒泡排序在函数式语言中一开始就效率不高。一位幽默愤世嫉俗的评论者还指出,冒泡排序仅适用于列表很小且无论如何都已排序的情况。
不过,我很好奇如何在 F# 中编写巧妙的冒泡排序,因为我过去曾在 C#、C++ 和 Java EE 中做过冒泡排序,而且我是 F# 新手。
在函数式语言中使用冒泡排序不是很有效,因为实现必须多次反转列表(对于不可变列表来说,这不能真正非常有效地实现)。
无论如何,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
Tomas
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)