qsort使用什么排序算法?
我找不到有关C qsort
函数使用的排序算法的任何信息。
它快速排序吗? 人类没有提到它。
未指定qsort
的实现:实现可以使用任何排序算法。 有趣的是,排序不需要稳定,也没有复杂性要求。
qsort
的整个规范(C11§7.22.5.2)如下:
qsort
function概要
#include
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); 描述
qsort
函数对nmemb
对象的数组进行nmemb
,其初始元素由base
指向。 每个对象的size
由size
指定。数组的内容根据compar指向的比较函数按升序排序,该函数使用两个指向被比较对象的参数调用。 如果第一个参数被认为分别小于,等于或大于第二个参数,则该函数应返回小于,等于或大于零的整数。
如果两个元素相等,则它们在生成的排序数组中的顺序是未指定的。
返回
qsort
函数不返回任何值。
理论上,qsort仅定义为qsort
和bsort
的返回值和调用值。 这是ISO标准参考。
在实践中,它通常使用quicksort 。
作为James McNellis对标准的引用的补充,值得注意的是, GNU的libc文档说明了
qsort
函数的名称源于它最初使用“快速排序”算法实现的事实。
并且它决定使用替代算法 ,显然是合并排序。