C : What is time complexity of qsort function?

Question

C 标准库中的 qsort 函数的复杂度是多少？如果可以的话，也请提供一个引用。

   #include <stdlib.h>
     void qsort(void *base, size_t nmemb, size_t size,
     int (*compar)(const void *, const void *));

Answer 1

根据cppreference.com ，这是有关 C 语言的文档的相当可靠的来源:

Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees.

我有一份 C ISO 标准草案，其中有关 qsort 的内容如下:

The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size.

The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

If two elements compare as equal, their order in the resulting sorted array is unspecified.

Returns:

The qsort function returns no value.

这支持引用站点的说法，因为这里没有提及任何复杂性保证。

因此，总的来说，您不能假设平均或最坏情况下的运行时间为 O(n log n)。历史上有一些使用启发式方法的实现，但在最坏的情况下可能会退化。搜索“快速排序的 killer 对手”了解详细信息。

将此与 C++ std::sort 进行对比，which is guaranteed to run in time O(n log n)在最坏的情况下。