F＃排序问题

Question

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

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

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

并返回： val it：int list = [1; 1; 2; 3; 4; 5; 5; 6; 9]

Answer 1

想想可以在第一位置结束了......现在它只能是在你的列表（if最后盒内）

Answer 2

你的代码是这样的第一或第二位置一个泡泡周期在bubble sort。这将需要最大的元素到最后的位置和一些其他更大的元素在右边。

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

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

Answer 3

let rec ssort = function 
    [] -> [] 
    | x::xs -> 
     let min, rest = 
      List.fold_left (fun (min,acc) x -> 
          if h<min then (h, min::acc) 
          else (min, h::acc)) 
       (x, []) xs 
     in min::ssort rest