qsort使用什么排序算法？

Question

我找不到关于C语言qsort函数使用的排序算法的任何信息。

它是快速排序吗？在手册中没有提到。

- good_evening

Answer 1

实现qsort没有具体规定: 实现可以使用任何排序算法。有趣的是，排序不需要稳定，并且没有复杂度要求。

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

qsort函数

概要

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

描述

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

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

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

返回值

qsort函数没有返回任何值。

- James McNellis

Answer 2

理论上，qsort仅定义了qsort和bsort的返回值和调用值。这里是ISO标准引用。（链接） 实际上，它通常使用快速排序算法。

- the wolf

Answer 3

补充一下James McNellis引用标准的内容，值得注意的是GNU libc文档中提到：

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

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

- kmkaplan