我遇到了一种叫做美国排序的排序算法。我读到它是基数排序的变体。有人可以详细说明这种排序算法以及与之相关的时间和空间复杂度吗。
最佳答案
您指的是 American flag sort ，一种高效的就地基数排序变体，可将项目分配到数百个桶中。这是一个分布排序:其中项目从输入分布到多个中间结构(在本例中为桶)，然后收集并放置在输出上。
基数排序:时间:O(nk)，空间:O(n+k)，n为key个数，k 是数字(值)可以具有的最大位数。
美国国旗排序:时间:O(n*k/d)，空间:O(k)，n为位数，k 是平均桶大小。
阅读更多 american flag sort optimization .
阅读Engineering Radix Sort (1993) ，论文中对两种算法进行了实验比较。
Java implementation美国国旗分类。
关于algorithm - 美式排序和基数排序有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50905010/