c++ - 关于搜索和排序算法的问题

Question

我正在对标准库中的搜索和排序算法进行一些研究。我找不到关于这些问题的信息。我希望有人能帮助我。如果您知道一些，也可以将链接发给我。

• 如果数据未排序与排序后的数据相比，搜索行为是否会发生变化？

• 我怎么知道在 vector 上使用 std::sort() 而不是将 vector 复制到已经排序的集合是否更好？那只是一个例子。我希望能在网上找到一些解释，说明哪些方法最适合搜索或排序，但我没有找到。

• 如何调整搜索和排序算法的行为以提高效率？

Answer 1

Does the searching behavior change if the data is not sorted compared to one which is sorted?

视情况而定。如果您按位置访问 vector/数组中的数据，则不会提高性能，也不需要进行排序。

可以线性、二进制、键和哈希函数进行搜索。

对于小的(我猜是低于几十个项目的东西)和连续的容器(例如 vector )线性搜索可能是最快的，只是因为缓存友好的内存布局。

二分搜索的复杂度为 O(log N)，这可能是你能得到的最好的……我在想 Information theory .它要求您预先对容器进行排序。这对于在同一容器中频繁搜索很有用。

std::set(及其堂兄 std::map)在内部使用树，这也使得搜索复杂度为 O(log N)。如果您通过键而不是项目的某些标准进行搜索，则很有用。缺点是构建(始终保持排序)比填充 vector 然后再排序要慢一些。

HashMap 或哈希表使用一个函数来获取项目所在的桶。复杂度接近于 O(1)，具体取决于项的数量和使用的函数(冲突问题)。

如您所见，选择容器类型取决于您将如何处理数据。选择符合您要求的一项。

How can I know if it is better to use std::sort() on a vector instead of maybe to copy the vector to an already sorted set?

std::sort 更改容器，因此结果显然是已排序的。如果您需要原始的、未排序的容器，请复制一份并对拷贝进行排序。对整个容器进行排序比对所有项目“插入项目如此容器始终排序”更好，特别是使用 vector (许多内存重新分配)；设置/ map 填充过程可能不会那么慢。

How can I adapt the behavior of the searching and sorting algorithms to make it more efficient?

我不太清楚你的意思。但是，“目的不择手段”。同样，选择最适合您的数据处理的容器。