c - qsort 使用什么排序算法？

Question

我找不到任何关于 Cqsort函数使用什么排序算法的信息。

是快速排序吗？在人中没有提到。

Answer 1

qsort未指定的实现：实现可以使用任何排序算法。有趣的是，排序不需要稳定，也没有复杂度要求。

(C11 §7.22.5.2)的整个规范qsort如下：

qsort功能_

概要

#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函数不返回任何值。

Answer 2

理论上，qsort 只定义到 and 的返回值和调用值的qsort地步bsort。以下是 ISO 标准参考。

在实践中，它通常使用快速排序。

Answer 3

作为对 James McNellis 对该标准的引用的补充，值得注意的是GNU 的 libc 文档说

该qsort函数的名称源于它最初是使用“快速排序”算法实现的。

并且它决定使用另一种算法，显然是合并排序。