我刚刚是不是在JavaScript上排序了O(n)

Did I just sort in O(n) on JavaScript?

本文关键字：是不是 JavaScript 排序      更新时间：2023-09-26

使用下划线库，我试图滥用JavaScript对象的索引，以便对整数或字符串的数组a进行排序:

_(a).chain().indexBy(_.identity).values().value()

我意识到这是一种"hack"，但它实际上在O(n)时间内产生了一个排序数组…

我在做梦吗?

您实际上没有对任何内容进行排序。

相反，您正在构建一个哈希表并按哈希顺序遍历它，这可能与某些集合的排序顺序相同。

可以使用桶排序http://en.wikipedia.org/wiki/Bucket_sort按O(n)排序，我相信这就是您在这里试图写的，但如上所述，您不能依赖于对象值的顺序。

如果值的数量有限，可以在O(n)内以这种方式排序

你的算法是不是比较排序:

比较排序是一种只读取对象的排序算法通过单个抽象比较操作(通常是a)列出元素"小于或等于"操作符或三方比较)决定两个元素中哪一个应该在决赛中先出现排序列表。

你在你的算法中使用关于值结构的知识(即知道它们是整数或字符串)，通过使用这些整数/字符串作为索引。您没有遵守对比较排序施加的限制，因此您在时间复杂度上不受O(n log n)边界的限制。

是的,你做梦:-)

很难相信你会偶然发现这样一个圣杯。如果该操作序列是基于比较的排序，知道这些东西的人实际上已经证明了它不能在O(n)时间内完成。

我强烈建议你运行数据集大小为10,100,1000等的代码，你会看到你的假设是不正确的。

然后检查你的是否真的在对数组进行排序，或者这只是它的组织的一个工件。似乎很可能indexBy只是简单地创建一个索引结构，其中顺序恰好是您想要的排序顺序，而不是保证所有输入的东西。
相关文章：