c - 对结构体数组进行排序或对结构体列表 C 进行排序，哪个更快？

Question

我面临着挑战。我有结构链接列表上的数据。我是将数据移动到结构数组中，然后使用 qsort() 对它进行排序还是使用合并排序？ 这是结构:

struct properties{
    char *path;
    char *name;
    char *extension;
    long int size;
    long unsigned created;
    long unsigned modified;
    long unsigned access;
    int permissions;
};

Answer 1

我将创建一个指向结构的指针数组，并使用qsort对指针数组进行排序。使用指针而不是复制整个结构将使用更少的内存。

创建一个像这样的比较器:

int propertyComparator(const void *s1, const void* s2) {
    struct property *p1 = (struct property *)s1, *p2 = (struct property *)s2;

    /* compare p1 and p2, below is just an example */
    int result = strcmp(p1->name, p2->name);
    return result;
}

这样调用它:

 struct property *array;
 /* add code to allocate and create array */
 qsort(array, num_elements, sizeof array, propertyComparator);

编辑:

如果你想要一个排序的链表，合并排序也差不多快。似乎这取决于链表的碎片程度。 请参阅https://stackoverflow.com/a/1525419/646887

我更喜欢qsort的原因是它是C库的一部分，所以我不必编写和维护那么多代码。而且它始终是一个快速的选择。