排序数组和indexOf()运行时间

Question

可以假设array.indexOf()从数组的开头开始进行线性搜索吗？

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

注：

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

“最大值”实际上是一个字符串，是最常用的搜索关键字。

- shinzou

---

如果你正在排序，就不应该使用 indexOf，而应该使用二分查找。 - Bergi

嗯... 对数组进行排序需要超过线性时间... 但如果您只排序一次并进行少数次搜索，那么这可能是有意义的... 另外，如果您只需要找到最大值，那么应该使用类似于最大堆的东西... 或者如果您需要查找不同值，则应使用二叉查找树。 - JCOC611

我所谓的“max”实际上是最受欢迎的搜索关键字，它是一个字符串，是的，我只想排序一次。@JCOC611 - shinzou

你的应用程序真的需要这种程度的优化吗？如果不需要，那就做最容易阅读和维护的事情，当出现性能问题时再进行故障排除。 - Michael L.

就性能而言，你尝试过lastIndexOf()了吗？它在某些情况下似乎比indexOf()表现更好...只是一个想法。 - Zathrus Writer

Answer 1

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

当然这取决于您的DataObject：

ArrayList：

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也可以在其始终排序时帮助您。

最后，我要说：“这取决于您的数据容器以及如何实现排序或搜索以及整个过程中性能的位置”。

作为评论，使用纯数组可以进行二进制搜索，其性能影响与快速排序相同。

因此，最后不仅是算法性能的问题，还涉及在何时需要该过程中的性能。例如，如果添加值时有很多时间而获取所需时间很少，则排序结构可以很好地改善它，例如树形集合。如果需要通过添加东西获得更高的性能，则情况可能正好相反。

- Henning Luther