搜索和排序向量的最快方法 [英] Fastest way to search and sort vectors

问题描述

我正在做一个项目，我需要在向量中插入数据并对它进行排序并进行搜索...

我需要尽可能快的算法来进行排序和搜索...我一直在搜索，发现std :: sort基本上是quicksort，它是最快的排序之一，但我不知道哪种搜索算法是最好的?二进制搜索?你能帮我吗?tnx ...所以我有3种方法:

  void addToVector(Obj o){fvector.push_back(o);}无效sortVector(){sort(fvector.begin()，fvector().end());}OBJ *搜索(字符串和bla){//我会在这里写二进制搜索返回binarysearch(..);} 

解决方案

---

• 我一直在搜索，发现具有相同的平均性能和最坏情况的性能(即，).还请记住，二进制搜索要求容器应按升序或降序排列.但是，是否比其他搜索方法(例如 ).我希望清楚地表明，最快"取决于许多因素.

• 使用 std :: sort 对您的 std :: vector .

• 对 std :: vector 进行排序后，请使用 std :: binary_search 来查找您的 std :: vector 或使用 std :: upper_bound 从您的 std ::中查找并获取元素.向量 .

I'm doing a project in which i need to insert data into vectors sort it and search it ...

i need fastest possible algorithms for sort and search ... i've been searching and found out that std::sort is basically quicksort which is one of the fastest sorts but i cant figure out which search algorithm is the best ? binarysearch?? can u help me with it? tnx ... So i've got 3 methods:

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(..);
}

解决方案

---

• I've been searching and found out that std::sort is basically quicksort.

  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::vector with 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: which has time complexity) depends on a number of factors. Some of them are:

  1. The number of elements/objects (see chart below).
  2. The type of elements/objects.

---

Bottom Line:

• Usually looking for the "fastest" algorithm denotes premature optimization and according to one of the "great ones" (Premature optimization is the root of all evil - Donald Knuth). The "fastest", as I hope it has been clearly shown, depends on quite a number of factors.

• Use std::sort to sort your std::vector.

• After sorting your std::vector use std::binary_search to find out whether a certain element exists in your std::vector or use std::lower_bound or std::upper_bound to find and get an element from your std::vector.

这篇关于搜索和排序向量的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！