javascript - 排序数组和 indexOf() 运行时

Question

假设 array.indexOf() 从数组的开头进行线性搜索是否安全？

所以如果我经常搜索最大值，在调用 indexOf 之前对数组进行排序是否会使它运行得更快？

注意事项:

我只想排序一次，搜索多次。

“最大的值(value)”实际上是最流行的搜索关键字，它是一个字符串。

Answer 1

是的，indexOf是从第一个开始到最后一个。根据排序算法的性能，在询问第一个条目之前对其进行排序会在性能上有所不同。通常，快速排序中的 O(N log N) 到线性搜索中的 O(n)。我建议您使用随机值计数对其进行简单测试，看看性能表现如何。

当然这取决于你的数据对象:数组列表:

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

也许 TreeSet 也可以帮助您一直订购。

最后我会说:“取决于您的数据容器以及排序或搜索的实现方式以及整个过程中需要性能的地方”。

正如评论所说，对于纯数组，您可以制作 binarySearch，它具有与快速排序相同的性能影响。

所以最后不仅仅是算法性能的问题，还有你在什么时候需要这个过程中的性能。例如，如果您有很多时间添加值而没有时间获取所需的值，则排序结构可以很好地改进它，例如 Tree-Collections。如果您需要通过添加东西来提高性能，则可能会反过来。