排序数组和indexOf（）运行时

可以安全地假设array.indexOf()从数组的开头进行线性搜索吗？排序数组和indexOf（）运行时

所以如果我经常搜索最大的值，在调用indexOf之前排序数组会让它跑得更快吗？

备注：

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

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

来源

2017-04-06 shinzou

如果你正在排序它，你不应该使用'indexOf'，但是二分搜索 – Bergi

呃...排序数组需要的不仅仅是线性时间......但是如果你排序一次并搜索几次，可能会使感觉......然后，如果你需要找到不同的值，那么你应该再次使用类似最大堆的东西，如果你只需要最大值...或二叉搜索树。 – JCOC611

那么我所说的“最大”实际上是最流行的搜索关键字是一个字符串，是的，我只想排序一次。 @ JCOC611 – shinzou

是的，indexOf从第一个开始到最后一个。在询问之后的第一个条目之前排序它会影响性能，这取决于排序算法的性能。在线性搜索中，快速排序中的O（N log N）通常为O（n）。我建议你用随机值计算一个简单的测试，看看性能如何表现。

当然这取决于你的数据对象：的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还可以帮助你，直到其下令所有的时间。

最后我会说：“取决于你的数据容器以及如何实现排序或搜索以及需要在整个过程中的性能表现。

作为一个评论说纯数组，你可以使binarySearch具有相同的性能影响快速排序。

所以最后它不仅是一个算法性能的问题，而且在什么时候你需要在这个过程中的性能。例如，如果通过获取所需的值来添加值而没有多少时间，则排序结构可以很好地改善它，如Tree-Collections。如果您需要更多的表现，可以通过添加其他方式来实现。

来源

2017-04-06 20:39:18

排序数组和indexOf（）运行时

回答

相关问题