sorting - Common Lisp 中的“排序”功能使用什么算法？

Question

我想，它可能取决于实现，所以这个问题并不完全正确。仍然看起来像是某种与 n(log n) 平均复杂度进行比较的排序。以更容易回答的方式重新表述我的问题：是否有任何理由编写自己的快速排序或合并排序或任何其他比较排序而不是说教？

Answer 1

是的，算法是实现定义的（想象在标准中规定了一个特定的算法，然后有人很长一段时间发明了一个更好的通用算法）。您可以自己查找标准（只需谷歌“clhs sort”）。

sort提供的实现stable-sort通常应该涵盖您拥有的几乎所有排序需求。我可以想象以下编写自己的原因：

• 您需要挂钩到排序过程的特定阶段
• 您只需要部分排序
• 您需要针对您的问题域的特定算法
• 您想比较不同的算法

无论如何，我应该建议深入研究现有的排序实现，以免错过可能的优化（这通常与排序上下文相关）。