2

这是文档：

val sort : ('a -> 'a -> int) -> 'a list -> 'a list

根据比较函数对列表进行升序排序。如果参数比较相等，比较函数必须返回 0，如果第一个较大，则返回正整数，如果第一个较小，则返回负整数（请参阅 Array.sort 以获取完整规范）。例如， compare 是一个合适的比较函数。结果列表按升序排序。List.sort 保证在恒定堆空间（除了结果列表的大小之外）和对数堆栈空间中运行。

当前实现使用合并排序。它在恒定堆空间和对数堆栈空间中运行。

val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list

与 List.sort 相同，但the sorting algorithm is guaranteed to be stable（即比较相等的元素保持其原始顺序）。

当前实现使用合并排序。它在恒定堆空间和对数堆栈空间中运行。

我想merge sort反正是稳定的，对吧？

OCaml 如何产生non-stable merge排序？

在non-statble merge sort版本中，它更快吗？

4

2 回答 2

6

归并排序是稳定的，但排序使用归并排序这一事实并不是其契约的一部分。请注意，它只说“当前实现使用......”。不能保证将来会继续使用合并排序，因此如果您List.sort在代码中使用，则无法保证排序会稳定，即使它在当前实现中可能碰巧是稳定的。

只要每个需要稳定排序的stable_sort代码都使用sort.

于 2013-02-22T17:28:21.953 回答
1

您需要将定义与实现分开。实现者保留更改实现的权利，并且非常小心和清楚地定义了函数的行为方式。

于 2013-02-22T17:28:54.573 回答