F#排序问题

Question

这段代码有什么问题吗？为什么不排序？

let rec sort = function
  | []         -> []
  | [x]        -> [x]
  | x1::x2::xs -> if x1 <= x2 then x1 :: sort (x2::xs)
                              else x2 :: sort (x1::xs)

支持采取 排序 [3;1;4;1;5;9;2;6;5];;

并返回: val it : int 列表 = [1; 1; 2； 3； 4； 5； 5； 6； 9]

Answer 1

你的代码就像 bubble sort 中的一个气泡循环。它将把最大元素带到最后一个位置，并将其他一些更大的元素放在右边。

请注意，您仅遍历原始列表一次。它具有线性复杂度，我们都知道仅使用比较进行排序必须是 O(n*log n)。

如果您想对此列表进行排序，可以多次重复该循环。