C++ - 将项添加到排序数组的最快方法

Question

我有一个大约有20万个项目的数据库,按用户名排序.现在,当我将一个项添加到数组的末尾并调用我的快速排序函数来对该数组进行排序时,几乎需要一秒的时间进行排序,这是不可接受的.肯定有一些可以做的优化.例如,如果我按顺序将每个字符串从n-1比较为0,然后相应地移动项目,则性能会更高.

其他的想法是我可以执行从0到n-1的二进制搜索,而不是infact搜索,但类似于利用我已经排序的数组.但是我没能编写一个合适的函数来返回一个索引,我的新元素应放在该索引中.

void quick_sort(int left, int right)
{
    int i = left, j = right;
    if (left >= right) return;
    char  pivotC[128];
    DataEntry *tmp;

    strcpy_a(pivotC, sizeof pivotC, User[(left + right) / 2]->username);

    while (i <= j)
    {
        while (StringCompare(User[i]->username, pivotC))
            i++;
        while (StringCompare(pivotC, User[j]->username))
            j--;
        if (i <= j) 
        {
            tmp = User[i];
            User[i] = User[j];
            User[j] = tmp;
            i++;
            j--;
        }
    }
    if (left < j)
        quick_sort(left, j);
    if (i < right)
        quick_sort(i, right);
}

任何帮助是极大的赞赏.

Answer 1

解决方案是重写你的代码以使用stl,我不明白为什么人们用C++编写C代码.

你需要一个用户矢量

std::vector<User> users;
//then you can keep it ordered at each insertion
auto it = upper_bound(users.begin(), users.end(), user_to_insert, 
    [](auto& lhs, auto& rhs ) { /* implementation left to the reader */});
users.insert(it, user_to_insert);

您现在可以以更好,更干净的方式使用相同的功能