C ++-将项目添加到排序数组的最快方法 [英] C++ - Fastest way to add an item to a sorted array

问题描述

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

I've got a database with approximately 200 000 items, which is sorted by username. Now when I add an item to end of array and call my quick sort function to sort that array it takes almost a second to sort, which is not acceptable. There are definitely quite some optimisations that can be done. For example if I sequentially compare each string from n-1 to 0, and then move items accordingly performance is much greater.

另一个想法是我可以执行从0到n-1的二进制搜索，但不是实际搜索，而是可以利用已经排序的数组的类似方法.但是，我没有编写适当的函数来返回应该放置新元素的索引.

Other idea is that I could perform binary search from 0 to n-1, well not infact search, but something similar to take advantage of my already sorted array. However I've failed to write a proper function that would return an index where my new element should be placed.

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

非常感谢您的帮助.

推荐答案

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

the solution is to rewrite your code to use the stl, I don't understand why people write C code in 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);

您现在可以以更简洁的方式拥有相同的功能

You now have the same functionality in a much nicer and clean way

这篇关于C ++-将项目添加到排序数组的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！