问如何在OCaml中使用list实现计数排序(O(n))？
EN

Stack Overflow用户

提问于 2013-04-14 05:02:50

回答 1查看 124关注 0票数 1

Counting sort使用数组，如果要排序的数字在已知范围内，则性能可以为O(n)。

但是，在OCaml中是否可以只使用list实现计数排序呢？

我的直觉是，可以在不使用可变数组的情况下使用list和map模拟counting sort，但性能不会是O(n)。

如果是这样的话，在不使用可变对象的情况下，counting sort真的对OCaml应用程序有帮助吗？

回答已采纳

发布于 2013-04-14 09:53:44

我相信，是的，没有数组是不可能实现O(n)计数排序的。你在问什么？

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15992893

复制

相似问题

问如何在OCaml中使用list实现计数排序(O(n))？EN