sorting - 是否有一个好的库可以在 C 中对大量数字进行排序？

Question

如果我有大量的整数或浮点数，那么什么是好的排序算法/实现（在 C 中）？

在游戏中进行编辑有点晚了......但我正在寻找正确性和速度。

Answer 1

标准库中的 qsort() 是一个很好的选择。

对于这些情况，比较函数将是微不足道的：

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

（编辑：这些基于从 a 中减去 b 的版本依赖于有符号的溢出行为，所以这不是一个好主意。）

Answer 2

对于数字数组的排序，请考虑基数排序算法。如果设计得当，这些排序应该提供比 GLIBC qsort() 更好的性能。

usort 库包含所有主要 C 数字类型的特定于类型的实现。

https://github.com/setjmp/usort

对于我的 64 位英特尔笔记本电脑上 N=1000000 的双精度浮点数，基数排序相对于 GLIBC qsort 的速度优势大约是 2.5 倍。然而，随着 N 的增长，优势应该会更大，因为基数排序是一种线性时间算法，需要恒定的数据传递次数。

对于非常小的 N，相同的代码分派到一个 introsort 或插入排序。

Answer 3

使用qsort绝不是一个坏主意……除非您对数字有所了解。

您已使用基数排序进行了标记。你准备投入多少内存？数字是否在特定范围内？它们是否具有使基数排序可行的特性？

除非您想使用大量内存，否则 qsort 是一个不错的选择。

Answer 4

鉴于我们现在获得的大量 RAM，以下设置排序是可能的：在一个巨大的 RAM 位数组中为您拥有的每个数字标记该位，然后通过扫描 RAM 将它们读回。许多特定于硬件的优化可以应用于标记和扫描阶段。