dplyr的arrange()使用什么排序算法？

Question

主要是出于好奇，我想知道 dplyr 的排列函数使用什么排序算法。我读到使用 R 的最常见的排序算法是选择排序，但我找不到有关range()的任何细节。我只是对排序算法有点兴趣，并且很好奇这个函数使用什么！

我查看了排列函数的源代码，但我无法真正判断该函数使用哪种排序方法。虽然我是 R 新手，所以这可能是显而易见的，但我无法告诉。我在 stackoverflow 上看到另一篇帖子问了这个问题，但不幸的是没有明确的答案它使用什么排序算法:) 谢谢！

Answer 1

dplyr::arrangeinherit是一个 S3 通用函数，它仅具有为数据帧（或类的对象"data.frame"，例如 tibbles）定义的方法。如果我们查看 的代码dplyr:::arrange.data.frame，我们会看到：

function (.data, ..., .by_group = FALSE, .locale = NULL) 
{
    dots <- enquos(...)
    if (.by_group) {
        dots <- c(quos(!!!groups(.data)), dots)
    }
    loc <- arrange_rows(.data, dots = dots, locale = .locale)
    dplyr_row_slice(.data, loc)
}

该函数实际上并不对任何东西进行排序；相反，它调用未导出的函数arrange_rows来对其进行排序。

查看代码arrange_rows（通过dplyr:::arrange_rows在控制台中输入），我们看到该函数本身将实际排序委托给另一个名为 的未导出函数vec_order_radix。

当我们查看该函数的代码时，我们发现它本身也不进行排序，而是调用一个 C 函数vctrs_order来通过接口进行排序.Call。

该函数在这里vctrs_order定义，从上面的代码注释我们可以看到，它根据传递的向量类型进行不同的调度。对于短向量（当前定义为少于 128 个元素），它将使用插入排序，对于较长向量，它将使用基数排序（整数向量除外，如果元素在 128 到 10000 之间，它将使用计数排序）。如果您选择，可以按照此处的 C 代码来详细检查它是如何完成的。

但最重要的是，R 代码中根本没有完成排序 - 它通常是用 C 实现的基数排序。