How*_*ard 42 sorting algorithm performance quicksort radix-sort
似乎Radix sort具有非常好的平均案例性能,即O(kN):http://en.wikipedia.org/wiki/Radix_sort
但似乎大多数人仍在使用Quick Sort,不是吗？
Ale*_* C. 18
根据你的评论编辑:
Meh*_*dad 17
这里的其他答案很可怕,他们没有给出实际使用基数排序的例子.
一个例子是使用偏斜DC3算法(Kärkkäinen-Sanders-Burkhardt)创建"后缀数组".如果排序算法是线性时间,则算法只是线性时间,并且基数排序在这里是必要和有用的,因为键是短的构造(3元组的整数).
除非你有一个巨大的列表或非常小的密钥,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)
小智 8
基数排序需要O(k*n)时间.但你必须问什么是K.K是"数字位数"(有点简单,但基本上就是这样).
那么,你有多少位数？相当多的回答,超过log(n)(使用"数字大小"作为基数的日志),这使得基数算法O(n log n).
这是为什么？如果您的数字小于log(n),那么您的数字可能少于n个.因此,您可以简单地使用"计数排序",这需要花费O(n)时间(只计算您拥有的每个数字的数量).所以我假设你有超过k> log(n)位数......
这就是为什么人们不使用Radix那么多.虽然有些情况下值得使用它,但在大多数情况下,快速排序要好得多.
小智 8
当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]??????????
}
}
小智 7
基数排序不是基于比较的排序，只能排序整数（包括指针地址）和浮点数等数字类型，并且可移植地支持浮点数有点困难。
可能是因为它的适用范围太窄，以至于很多标准库都选择省略它。它甚至不能让您提供自己的比较器，因为有些人甚至可能不想直接对整数进行排序，而是将整数用作其他东西的索引以用作排序的键，例如基于比较的排序允许所有这种灵活性，所以它可能只是更喜欢适合 99% 人们日常需求的通用解决方案，而不是为了迎合那 1% 的需求而竭尽全力。
也就是说，尽管适用性很窄，但在我的领域中，我发现基数排序比 introsorts 或 quicksorts 更有用。我在这 1% 中，几乎从不使用字符串键，但经常会发现从排序中受益的数字用例。这是因为我的代码库围绕实体和组件（实体-组件系统）的索引以及索引网格之类的东西展开，并且有大量的数字数据。
因此，在我的情况下，基数排序对各种事情都很有用。在我的案例中，一个常见的例子是消除重复索引。在那种情况下，我真的不需要对结果进行排序，但基数排序通常可以比替代方法更快地消除重复项。
另一个是寻找，比如说，沿着给定维度对 kd 树进行中值分割。对给定维度的点的浮点值进行基数排序后，我可以在线性时间内快速获得一个中值位置来分割树节点。
z如果我们不打算在片段着色器中执行此操作，另一种方法是对更高级别的基元进行深度排序，以获得半正确的 alpha 透明度。这也适用于 GUI 和矢量图形软件的 z 顺序元素。
另一个是使用索引列表的缓存友好顺序访问。如果索引被多次遍历，如果我提前对它们进行基数排序，则通常会提高性能，以便按顺序而不是随机顺序进行遍历。后者可以在内存中来回曲折，从缓存行中逐出数据，只是为了在同一循环中重复重新加载同一内存区域。当我在重复访问索引之前先对索引进行基数排序时，这种情况不再发生，我可以大大减少缓存未命中。这实际上是我最常使用的基数排序，当系统想要访问具有两个或更多组件的实体时，它是我的 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 实现基数排序，尽管我不知道他们是如何做到的。我不够聪明，无法提出这样的解决方案，尽管与标准库相比，即使是我天真的小基数排序也做得很好。
Guy*_*Nir -12
快速排序的平均时间为 O(N logN)，但最坏情况也为 O(N^2)，因此即使在大多数实际情况下它不会达到 N^2，也始终存在输入的风险对你来说将会处于“糟糕的状态”。这种风险在基数排序中不存在。我认为这给基数排序带来了很大的优势。