qsort()函数提供性能保证吗？

Question

C 标准是否要求标准库

qsort()

函数提供特定级别的性能？顾名思义，使用 O(n log n) 算法，例如“快速排序”。符合标准的库可以使用 O(n^2) 插入排序，甚至 O(n!) bogosort 来实现它吗？

Answer 1

这是来自 C89 标准的语言，位于标题 7.10.5.2 下。其他标准包含相同的语言。

剧情简介

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

描述

qsort函数对nmemb对象数组进行排序，其初始元素由base指向。每个对象的大小由 size 指定。

数组的内容根据 compar 指向的比较函数按升序排序，该函数使用两个指向被比较对象的参数来调用。如果第一个参数被认为分别小于、等于或大于第二个参数，则该函数应返回小于、等于或大于零的整数。

如果两个元素比较相等，则它们在排序数组中的顺序未指定。

退货

qsort 函数没有返回值。

我将此解释为 Bogosort 是一种符合标准的 qsort 实现方式。