美国排序和基数排序有什么区别？

Question

3

我发现一种叫做美国排序的排序算法，据说是基数排序的一种变体。可以有人详细介绍一下这个排序算法以及相关的时间和空间复杂度吗？

- Piyush Bhangale

1

这就是吗？https://en.wikipedia.org/wiki/American_flag_sort - Grimxn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gsamaras · Accepted Answer

您正在提到的是美国国旗排序，它是一种高效的原址基数排序变体，可以将项目分配到数百个桶中。这是一种分布式排序，其中项目从输入分发到多个中间结构（在此情况下是桶），然后被收集并放置在输出上。

基数排序：时间复杂度为O(nk)，空间复杂度为O(n+k)，其中n是键的数量，k是数字（值）可以拥有的最大位数。 美国国旗排序：时间复杂度为O(n*k/d)，空间复杂度为O(k)，其中n是数字的位数，k是平均桶大小。

阅读Engineering Radix Sort (1993)，该论文介绍了两种算法之间的实验比较。

Java 实现的美国国旗排序。