list - 使用一个递归函数和 FoldBack 函数实现插入排序

Question

我正在审查一些基本数据结构的实现以及对其进行操作的算法。我猜插入排序的惯用 F# 代码非常类似于:

let rec insert x = function
  | [] -> [x]
  | y::ys -> if x<=y then x::y::ys
             else y::(insert x ys)

and insertionSort = function
  | [] -> []
  | x::xs -> insert x (insertionSort xs)

let myLst = [8;3;3;5;-6;0;1;4;-3;2]
let result = myLst |> insertionSort 

验证结果:int list = [-6; -3; 0; 1; 2； 3； 3； 4； 5； 8]

当我尝试使用 List.foldBack 和只有一个递归函数来实现它时，如下所示，无法给我正确的结果？任何人都可以找出问题出在哪里吗？

let rec anotherInsertionSort lst =
  List.foldBack(fun x (ys:list<_>) -> 
                  if ys.IsEmpty then [x]
                  elif x <= ys.Head then x::ys
                  else ys.Head::x::anotherInsertionSort ys.Tail) lst []

Answer 1

从cfern's code未打高尔夫球:

let rec insert i = function
  | h::t -> min h i::(insert (max h i) t)
  | _ -> [i]

let insertionSort l = List.foldBack insert l []