2

输入：未排序列表/输出：排序列表

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

（如果我可以将第一个元素插入排序的尾部，我可以对列表进行排序。）

我使用了“插入”，它是辅助函数。

但是，它会溢出。谁能告诉我问题是什么？

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)) ;;
4

3 回答 3

8

同样，我有风格建议：

  • 您应该将这两个函数分开sort，insert因为它会使其更具可读性，并且因为该insert函数本身就很有用。
  • 为什么要给insert函数一个元组作为参数？在 OCaml 中，人们会使用 currying 和 writeinsert x l而不是insert(x,l). 这将允许您进行部分应用。
  • 为什么将函数的类型限制为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)
于 2013-04-10T10:32:58.243 回答
4

这条线对我来说看起来很错误：

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

在我看来，你知道你ys的排序（通过归纳假设）。因此，您应该n与您的 比较ys，而不是ys彼此比较。如果你把这条线理顺，事情可能会有所改善。

对于它的价值，我怀疑你只需要在你的match. 我不明白为什么需要将 1 元素列表与任何其他非空列表区别对待。

于 2013-04-10T01:30:46.180 回答
2

总是在问这样的问题时，人们很难阅读这样的代码，而且大多数情况下他们会忽略该帖子。就像@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 []
于 2017-03-19T17:44:06.590 回答