c - qsort() 使用哪种排序算法？

Question

该功能是否qsort()在stdlib.h实际上使用快速排序算法，顾名思义？

Answer 1

qsort() 函数可以使用库实现者选择的任何排序算法来实现，但名称表明该算法应该接近最优。使用 O(N²) 算法是允许的，但这是一个主要的 QoI(实现质量)问题。

值得注意的是，使用 qsort() 接口(interface)进行比较的成本相当高；任何增加比较次数以减少移动次数的排序算法(如果不打乱指针，这也可能是昂贵的)可能会导致性能下降。然而，这是库实现者需要关心的一个问题。除非您发现该库的实现很糟糕(现在这种情况不太可能发生)，否则请使用它并且不用担心。

C++ sort 算法可以围绕 C 的 qsort 运行环。