functional-programming - OCaml 中的排序函数是否使用不可变或可变数据结构？

Question

OCaml在实现排序时是否使用mutable或数据结构？immutable

对于许多排序算法，我们需要在列表或数组之类的位置之间交换数据。

我只是想知道，如果 OCaml 总是打算使用immutable data structures，那么每次交换操作都会创建一个新副本？

会影响performance吗？

Answer 1

对于许多排序算法，我们需要在列表或数组之类的位置之间交换数据。

不必要。

我只是想知道，如果 OCaml 总是打算使用不可变的数据结构

不，OCaml 具有可变和不可变的数据结构。不过，通常首选使用不可变数据结构。

那么每次交换操作都会创建一个新副本吗？

这将取决于所讨论的数据结构。但一般来说，在使用不可变数据结构时，您不希望通过交换单个元素来表达您的排序算法（正如我在上面指出的，您当然不需要）。

List.sort例如适用于不可变的数据结构（列表）并且非常有效。它使用归并排序算法（在当前的 OCaml 实现中）。