sorting - table.sort 使用什么算法？

Question

我很好奇 Lua 默认table.sort使用什么算法，只是因为它比我遇到的其他一些排序算法慢。我也很好奇 Luatable.sort是用 C 语言在引擎中编写的，还是在 Lua 的库中。

Answer 1

table.sort 使用什么算法？

（向上滚动一点）中的评论指出tablib.c

/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
**  Addison-Wesley, 1993.)
** =======================================================
*/

您可以在我提供的链接中阅读源代码。

我也很好奇 Lua 的 table.sort 是用 C 语言在引擎中编写的，还是在 Lua 的库中。

目前，所有 Lua 直接自带的库（io, table, math, ...）都是用 C 编写的。

Answer 2

在内部，table.sort使用快速排序，它是用 C 编写的。请注意，快速排序不是稳定的。让我有点惊讶的是，Lua 并没有qsort()直接使用 C。

至于性能，很难说，因为有多种因素，例如，您要比较的语言和算法，以及正在测试的数据类型。