什么更快：使用快速排序然后使用二分搜索还是仅使用线性搜索？
What Is Quicker: Using Quicksort then Binary Search OR Just Linear Search?
如果我有一个包含 1000 个元素的整数数组，查找特定元素索引的最快方法是什么？最好先对其进行 QuickSort 然后使用 BinarySearch 还是只使用普通的旧 LinearSearch？
此外，如果我有 100 000 个元素或什至只有 100 个元素，最快的方法会有所不同吗？
谢谢！
线性搜索会更好。线性搜索 O(N) 的最坏情况小于单独的快速排序（平均 O(nlog n) 但最坏情况 O(N^2)） 和 然后你需要添加二进制搜索（O(log N)）。如果需要多次搜索，排序和使用二分搜索会更好（如果可以分摊排序成本，那么二分搜索比线性搜索更有效）。
快速排序计算开销在最佳情况下为 O(nlog(n))，在最坏情况下为 O(n^2)，二分查找为 O(log(n))最坏的情况是 O(n^2).
无需提及线性搜索需要 O(n)
所以这取决于你的操作次数和输入大小。您可以乘以两种最坏情况下的平均搜索次数（kW(n)，其中 k 是搜索次数，n 是数组大小，W(n) 是每种方法的最坏情况），然后决定怎么办。
正如其他答案所说，线性搜索更好如果您只想查找列表中的一个成员。但是如果你想在同一个列表中找到很多成员，那么你最好先排序一次，然后再进行多次二进制搜索。
使用线性搜索更快，因为与单独使用快速排序所消耗的 O(nlogn) 时间相比，它需要 O(n)。但是，要在元素数量较多的情况下缩短时间，请尝试并行创建多个数组块和 运行 搜索算法。查看 PPL（Stl 库）了解更多信息。
线性搜索会将每个项目与另一个项目进行比较以找到相应的索引。
快速排序首先将每个项目与主元进行比较，以便执行第一个分区步骤。之后还有更多的操作。
第一步快速排序的时间已经和整个线性搜索一样多，所以至少和线性搜索一样长。对于不同的列表大小，这将是相同的。
如果我有一个包含 1000 个元素的整数数组，查找特定元素索引的最快方法是什么？最好先对其进行 QuickSort 然后使用 BinarySearch 还是只使用普通的旧 LinearSearch？
此外，如果我有 100 000 个元素或什至只有 100 个元素，最快的方法会有所不同吗？
谢谢！
线性搜索会更好。线性搜索 O(N) 的最坏情况小于单独的快速排序（平均 O(nlog n) 但最坏情况 O(N^2)） 和 然后你需要添加二进制搜索（O(log N)）。如果需要多次搜索，排序和使用二分搜索会更好（如果可以分摊排序成本，那么二分搜索比线性搜索更有效）。
快速排序计算开销在最佳情况下为 O(nlog(n))，在最坏情况下为 O(n^2)，二分查找为 O(log(n))最坏的情况是 O(n^2).
无需提及线性搜索需要 O(n)
所以这取决于你的操作次数和输入大小。您可以乘以两种最坏情况下的平均搜索次数（kW(n)，其中 k 是搜索次数，n 是数组大小，W(n) 是每种方法的最坏情况），然后决定怎么办。
正如其他答案所说，线性搜索更好如果您只想查找列表中的一个成员。但是如果你想在同一个列表中找到很多成员，那么你最好先排序一次，然后再进行多次二进制搜索。
使用线性搜索更快，因为与单独使用快速排序所消耗的 O(nlogn) 时间相比，它需要 O(n)。但是，要在元素数量较多的情况下缩短时间，请尝试并行创建多个数组块和 运行 搜索算法。查看 PPL（Stl 库）了解更多信息。
线性搜索会将每个项目与另一个项目进行比较以找到相应的索引。
快速排序首先将每个项目与主元进行比较，以便执行第一个分区步骤。之后还有更多的操作。
第一步快速排序的时间已经和整个线性搜索一样多，所以至少和线性搜索一样长。对于不同的列表大小，这将是相同的。