强制 C 库 qsort 执行快速排序而不是合并排序

Question

我是 C 的新手，我正在阅读这篇文章 post： Killing Quicksort

它说：

A note of caution for those playing along at home: the GNU C library qsort function is actually mergesort if the C library thinks the computer has enough free memory; to force quicksort, call the undeclared _quicksort function and compile with gcc -static.

关于我使用 CMake 的编译器选项，我已将 cmake 标志设置为：

set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -std=gnu99 -static")

但我不确定如何调用未声明的 _quicksort.

有人有这方面的经验吗？

修复：

我刚刚按照@recycler 建议的方式声明了 _quicksort 函数：

void _quicksort(void *__base, size_t __nmemb, size_t __size,
        __compar_fn_t __compar);

现在它的行为似乎像一个快速排序。我是 C 的初学者，对我来说这似乎很神奇，但无论如何，我认为自己现在已经很满意了。

Answer 1

您可以在您的 C 测试代码中声明函数“_quicksort”。这应该与 qsort 相同。现在你必须 link 它针对 c-lib，这应该由 linker 自动完成。如果函数 _quicksort 被导出，它可以被使用并且 linker 将 link 它到你的二进制文件。如果未导出，则会出现错误。

这是快速而肮脏的选择。您还可以阅读 GNU C 库的源代码。也许还有其他选择。

Answer 2

请注意 - 你的里程可能会有所不同，但我刚刚测试了 glibc 版本的 _quicksort 和 mergesort 在所有不同的大小和随机数组中，按顺序，在 anti-order 中。 mergesort 总是比 _quicksort 快 25%。这可能就是他们更换它的原因。 ;)

强制 C 库 qsort 执行快速排序而不是合并排序

Force C library qsort to perform a quicksort rather than a mergesort

c

qsort