Ocaml插入排序

Question

输入:未排序列表/输出:已排序列表

我的基本想法是在排序列表中插入一个整数。

(如果我可以将第一个元素插入到排序的尾部中，我就可以对列表进行排序。)

我使用了"insert"，这是thehelper函数。

但是，它会溢出。谁能告诉我问题出在哪里？

let rec sort (l: int list) : int list =
    match l with
        []->[]
      | x::[]->[x]
      | x1::x2::xs->let rec insert (n,dest) =
                            match dest with
                                []->[n]
                              | y::[]-> if n<y then [n;y] else [y;n]
                              | y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)
                    in insert(x1,sort(x2::xs)) ;;

Answer 1

在我看来，这一行很不对劲：

| y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)

在我看来，您知道您的ys是排序的(根据归纳假设)。因此，您应该将n与您的ys进行比较，而不是将您的ys彼此进行比较。如果你弄清楚了这条线，事情可能会有所改善。

无论如何，我怀疑您的match中只需要有两个cases。我不明白为什么您需要将1元素列表与任何其他非空列表区别对待。

Answer 2

再一次，我有一些风格建议：

• 你应该把sort和insert这两个函数分开，因为这样会使它更具可读性，而且insert函数本身也很有用。
• 为什么要把一个元组作为参数给insert函数呢？在OCaml中，可以使用currying并编写insert x l，而不是insert(x,l)。这将允许你做部分application.
• Why，你是否将你的函数类型限制为int list -> int list。OCaml中的函数可以是多态的，因此您的函数应该具有更泛型的类型'a ist -> 'a list.

以下是您通过所有这些更正获得的代码：

let rec insert x l =
  match l with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys

let rec sort l =
  match l with
    | [] -> []
    | x::xs -> insert x (sort xs)

Answer 3

总是在问这样的问题时，人们很难阅读这样的代码，而且大多数情况下他们会忽略帖子。就像@Thomash所说的，首先试着划分成更小的函数，这样更容易看到它失败的地方。

你可以这样“用眼睛调试”：

let rec insertion_sort el = function  
    | [] -> [el]
    | h::t as ls -> if el > h then h :: insert el t else (el :: ls) 

let sorted_list ls = List.fold_right insertion_sort ls []