我正在做一个项目，其中我需要将数据插入向量中，对其进行排序并搜索......
我需要最快的排序和搜索算法...我一直在搜索并发现 std::sort 基本上是快速排序，这是最快的排序之一，但我无法弄清楚哪种搜索算法是最好的？二分查找??你能帮我吗？ tnx ...所以我有3种方法：
void addToVector(Obj o)
{
fvector.push_back(o);
}
void sortVector()
{
sort(fvector.begin(), fvector().end());
}
Obj* search(string& bla)
{
//i would write binary search here
return binarysearch(..);
}
- 我一直在寻找并发现std::sort基本上是 快速排序。
块引用>Answer: Not quite. Most implementations use a hybrid algorithm like introsort, which combines quick-sort, heap-sort and insertion sort.
- Quick-sort is one of the fastest sorting methods.
Answer: Not quite. In general it holds (i.e., in the average case quick-sort is of
complexity). However, quick-sort has quadratic worst-case performance (i.e.,
). Furthermore, for a small number of inputs (e.g., if you have a
std::vectorwith a small numbers of elements) sorting with quick-sort tends to achieve worst performance than other sorting algorithms that are considered "slower" (see chart below):
- I can't figure out which searching algorithm is the best. Is it binary-search?
Answer: Binary search has the same average and worst case performance (i.e.,
). Also have in mind that binary-search requires that the container should be arranged in ascending or descending order. However, whether is better than other searching methods (e.g., linear search which has
time complexity) depends on a number of factors. Some of them are:
- 元素/对象的数量（见下图）。
- 元素/对象的类型。
底线：
通常寻找“最快”算法表示过早优化，并根据“伟大的算法”之一（过早的优化是万恶之源——唐纳德·高德纳）。正如我希望已经清楚地表明的那样，“最快”取决于很多因素。
Use std::sort对你的进行排序std::vector.
对你的排序后std::vector use std::binary_search找出某个元素是否存在于您的std::vector or use std::lower_bound or std::upper_bound从您的中查找并获取元素std::vector.