C++ 排序类比 qsort 更快

Question

我有课

class Zaposlenik { 
private:
    string prezime; 
    string funkcija; 
    double placa; 
public:
    bool operator==(const string& prezime) const; 
    bool operator<(const string &prezime) const; 
    bool operator<(const Zaposlenik &other) const; 

我使用带有字符串的运算符进行二分查找，使用带有 Zaposlenik 的运算符<进行排序

我无法更改 header 类我只能在.cpp 中编写代码。

我也有

class Firma { 
private: 
vector<Zaposlenik> zaposlenici; 
public: 
void sort();

我也不能改变那个类，我必须为它写.cpp。我将 2.cpp 上传到自动分级服务器，该服务器将 500 000 Zaposlenik 输入到 vector zaposlenici，然后执行 2 000 000 次搜索。

我使用了 qsort 和 bsearch，但速度太慢了。上传时不能超过3s。

我写过重载运算符，我相信它们没问题，但显然 qsort 可以更快。

vector 按字符串首字母排序，名称从“aaaa”到“ZZZZ”，因此大小写字母的 4 个字母组合。

string funkcija; 和 double placa; 对排序没有任何意义。

有人能告诉我哪种排序比 qsort 更快吗？请记住，我对 main 没有任何控制权，并且在创建成员时我无法对其进行计数。

附言类中还有其他函数，但它们对这部分没有任何意义。Bsearch 也有功能，但我相信它的速度是最快的。

Answer 1

三件事:

• 使用 std::sort它比 std::qsort 更快，因为它可以内联调用比较运算符(如果您在 header 中定义它或启用链接时优化)。

• Override swap为您的类(class)，以便可以有效地交换它，而不是通过临时变量进行复制。但是，这需要更改 header (因为您需要访问私有(private)变量)。

• 由于您排序的字符串的长度固定为 4，因此使用不同的排序算法会有所帮助。相当容易实现的经典选择是 radix sort .从您的一些评论来看，您的教授似乎希望您实现这一点。