什麼是F＃中最優雅的氣泡排序方式？

Question

F＃中最優雅的氣泡排序方式是什麼？

UPDATE

如答案之一指出，泡沫排序不是在功能語言開始與高效。一個幽默而憤世嫉俗的評論者也指出，泡泡分類只適用於名單很小且無論如何都幾乎分類的情況。因爲我在過去使用C＃，C++和Java EE進行了冒泡排序，並且由於我是F＃中的一員，所以我很想知道如何在F＃中編寫巧妙的冒泡排序，新手。

Answer 1

在函數式語言中使用冒泡排序並不是非常有效，因爲實現必須多次顛倒列表（並且這對於不可變列表來說不能非常有效地實現）。

無論如何，從二郎的例子可以改寫爲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 

托馬斯