performance - 我们什么时候应该使用基数排序？

Question

似乎基数排序具有非常好的平均案例性能，即O(kN)：http ://en.wikipedia.org/wiki/Radix_sort

然而，似乎大多数人仍在使用快速排序——这是为什么呢？

Answer 1

基数排序比大多数其他排序算法更难概括。它需要固定大小的密钥，以及一些将密钥分解成碎片的标准方法。因此，它永远无法进入图书馆。

Answer 2

这里的其他答案没有给出实际使用基数排序的例子。

例如，使用 skew DC3 算法 (Kärkkäinen-Sanders-Burkhardt) 创建“后缀数组”时。如果排序算法是线性时间的，则该算法仅是线性时间的，并且基数排序在这里是必要且有用的，因为键在构造上很短（整数的 3 元组）。

Answer 3

根据您的评论编辑：

• 基数排序仅适用于整数、固定大小的字符串、浮点数以及“小于”、“大于”或“字典顺序”的比较谓词，而比较排序可以适应不同的顺序。
• k 可以大于 log N。
• 快速排序可以就地完成，基数排序变得效率较低。

Answer 4

除非您有一个巨大的列表或非常小的键，否则 log(N) 通常小于 k，它很少会高很多。因此，选择具有 O(N log N) 平均案例性能的通用排序算法并不一定比使用基数排序更差。

更正：正如@Mehrdad 在评论中指出的那样，上面的论点并不合理：要么密钥大小是恒定的，那么基数排序是 O(N)，或者密钥大小是 k，那么快速排序是 O(k N log N)。所以理论上，基数排序确实有更好的渐近运行时间。

在实践中，运行时将由以下术语主导：

• 基数排序：c1 k N

• 快速排序：c2 k N log(N)

其中 c1 >> c2，因为从较长的密钥中“提取”位通常是一项昂贵的操作，涉及位移和逻辑操作（或至少未对齐的内存访问），而现代 CPU 可以将密钥与 64、128 甚至 256 位进行比较在一次操作中。因此对于许多常见情况，除非 N 很大，否则 c1 将大于 c2 log(N)

Answer 5

基数排序需要 O(k*n) 时间。但是你必须问什么是 K。K 是“位数”（有点简单，但基本上是这样的）。

那么，你有多少位数呢？很好的答案，不仅仅是 log(n)（使用“数字大小”作为基础的 log），这使得 Radix 算法 O(n log n)。

这是为什么？如果您的数字少于 log(n)，那么您的可能数字少于 n。因此，您可以简单地使用需要 O(n) 时间的“计数排序”（只需计算您拥有的每个数字的数量）。所以我假设你有超过 k>log(n) 个数字......

这就是为什么人们不那么多使用 Radix 排序的原因。尽管在某些情况下值得使用它，但在大多数情况下，快速排序要好得多。

Answer 6

当 n > 128 时，我们应该使用 RadixSort

排序 int32s 时，我选择基数 256，所以 k = log(256, 2^32) = 4，明显小于 log(2, n)

在我的测试中，基数排序在最好的情况下比快速排序快 7 倍。

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}

Answer 7

基数排序不是基于比较的排序，只能对整数（包括指针地址）和浮点数等数字类型进行排序，并且移植支持浮点有点困难。

可能是因为它的适用范围太窄，许多标准库选择省略它。它甚至不能让您提供自己的比较器，因为有些人可能甚至不想直接对整数进行排序，而是将整数用作其他东西的索引以用作排序的键，例如基于比较的排序允许所有这种灵活性，所以它可能只是更喜欢一个通用的解决方案来满足人们 99% 的日常需求，而不是竭尽全力满足这 1% 的需求。

也就是说，尽管适用性很窄，但在我的领域中，我发现基数排序比 introsorts 或 quicksorts 更有用。我属于那 1% 的人，几乎从未使用过字符串键，但经常会找到受益于排序的数字的用例。这是因为我的代码库围绕实体和组件的索引（实体组件系统）以及索引网格之类的东西，并且有大量的数字数据。

结果，基数排序在我的情况下对各种事情都很有用。在我的例子中，一个常见的例子是消除重复索引。在这种情况下，我真的不需要对结果进行排序，但通常基数排序可以比其他方法更快地消除重复项。

另一个是寻找，比如说，沿着给定维度的 kd 树的中值分割。对给定维度的点的浮点值进行基数排序后，我可以在线性时间内快速找到中值位置来拆分树节点。

z如果我们不打算在片段着色器中这样做，另一个是通过半正确的 alpha 透明度对高级基元进行深度排序。这也适用于 z 顺序元素的 GUI 和矢量图形软件。

另一个是使用索引列表的缓存友好顺序访问。如果索引被遍历多次，如果我提前对它们进行基数排序，通常会提高性能，以便按顺序而不是随机顺序完成遍历。后者可以在内存中来回曲折，从缓存行中逐出数据，只是为了在同一个循环中重复重新加载同一个内存区域。当我在重复访问它们之前首先对索引进行基数排序时，这种情况就不会发生了，我可以大大减少缓存未命中。这实际上是我对基数排序最常见的用途，当系统想要访问具有两个或更多组件的实体时，它是我的 ECS 对缓存友好的关键。

就我而言，我有一个经常使用的多线程基数排序。一些基准：

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

我可以平均大约 6-7 毫秒在我的小硬件上对一百万个数字进行一次排序，这并不像我想要的那么快，因为有时在交互式环境中用户仍然可以注意到 6-7 毫秒，但仍然是一个整体比 55-85 毫秒要好很多，就像 C++std::sort或 C 的情况一样qsort，这肯定会导致帧速率非常明显的打嗝。我什至听说有人使用 SIMD 实现基数排序，但我不知道他们是如何做到的。我不够聪明，无法提出这样的解决方案，尽管与标准库相比，即使是我天真的小基数排序也做得很好。

Answer 8

k = "要排序的数组中最长值的长度"

n = "数组长度"

O(k*n) = "最坏情况运行"

k * n = n^2（如果 k = n）

因此，在使用基数排序时，请确保“最长整数比数组大小短”，反之亦然。然后你要打败快速排序！

缺点是：大多数时候你不能保证整数有多大，但如果你有一个固定的数字范围，基数排序应该是要走的路。

Answer 9

这是一个比较快速排序和基数排序的链接：

基数排序比整数数组的快速排序快吗？（是的，2-3x）

这是另一个分析几种算法的运行时间的链接：

分类问题：

在相同的数据上哪个更快；O(n) 排序还是 O(nLog(n)) 排序？

答：视情况而定。这取决于被排序的数据量。它取决于运行它的硬件，也取决于算法的实现。

Answer 10

一个例子是当您对一组非常大的整数或整数数组进行排序时。基数排序和任何其他类型的分布排序都非常快，因为数据元素主要被排入队列数组（LSD 基数排序最多 10 个队列）并重新映射到要排序的相同输入数据的不同索引位置。没有嵌套循环，因此随着要排序的数据输入整数的数量变得明显更大，该算法倾向于表现得更线性。与其他排序方法不同，比如效率极低的bubbleSort方法，基数排序没有实现比较操作来排序。它只是一个简单的过程，将整数重新映射到不同的索引位置，直到最终对输入进行排序。如果您想自己测试 LSD 基数排序，我已经写了一个并存储在 github 上，可以在在线 js ide 上轻松测试，例如 eloquent javascript 的编码沙箱。随意玩弄它并观察它在不同数量的 n 下的表现。我测试了多达 900,000 个未排序的整数，运行时间 < 300 毫秒。如果您想玩它，这里是链接。

https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6

Answer 11

在 Integer 32bit Sort 中，它会快速排序 7-10 次，但在 1b 元素上会占用显着的内存，比如几个 gb 。因此，只有当您的数据 n 很大但数据中的原始值很小时，您才可以首先使用 Radix 或 Counter 排序，或者当您可以用内存换取速度时，您可以在任何巨大的整数列表排序中使用

Answer 12

快速排序的平均值为 O(N logN)，但它也有 O(N^2) 的最坏情况，因此即使在大多数实际情况下它也不会达到 N^2，但输入总是存在风险对你来说将是“坏秩序”。这种风险在基数排序中不存在。我认为这为基数排序提供了很大的优势。