qsort()性能问题

Question

我正在成功地对一个结构数组进行排序，其中每个结构只包含一个字符字符串。然而，我的问题是，对于一个结构数组的大约。900,000个元素，qsort花费的时间比我预期的要长(qsort需要大约2分钟来对这个数组进行排序)；这使我认为这里有我正在忽略的东西。排序是我正在做的作业中的一个琐碎的部分，并且完全超过了我的程序的时间限制。

下面是我代码的相关部分：

struct WordsArray //Just a struct thath holds a *char
{
    char word[25];
};

传递给qsort的比较函数：

int cmpfunc(const void *a, const void *b)
{
    const struct WordsArray *a1;
    a1 = (WordsArray*)malloc(sizeof(WordsArray));
    const struct WordsArray *b1;
    b1 = (WordsArray*)malloc(sizeof(WordsArray));
    a1 = (struct WordsArray*)a;
    b1 = (struct WordsArray*)b;

    return strcmp(a1->word, b1->word);
}

我打电话问：

WordsArray *AllWordsArray;
AllWordsList = (WordsArray*)malloc(sizeof(WordsArray)*ListSize);
qsort(AllWordsList->word, ListSize, sizeof(struct WordsArray), cmpfunc);

谢谢你的意见。

Answer 1

问题在于cmpfunc的实现:它比消防栓更快地泄漏内存！

您分配(WordsArray*)指针只是为了在下一行上对它们进行写入，从而在进程中造成内存泄漏。您所需要做的就是删除malloc：

int cmpfunc(const void *a, const void *b) {
    const struct WordsArray *a1 = (struct WordsArray*)a;
    const struct WordsArray *b1 = (struct WordsArray*)b;
    return strcmp(a1->word, b1->word);
}