我遇到了这种称为美式排序的排序算法。我读到它是基数排序的一种变体。有人可以详细说明一下这种排序算法以及与之相关的时间和空间复杂度吗？
您指的是“美国国旗排序”，它是基数排序的一种高效、“就地”变体，可将项目分配到数百个桶中。它是一个分布排序：其中项目从输入分布到多个中间结构（在本例中为桶），然后将其收集并放置在输出上。 基数排序
：时间：O(nk)，空间：O(n+k)，n是键的数量，k是数字（值）可以拥有的最大位数。
美国国旗排序：时间：O(n*k/d)，空间：O(k)，
n是位数，k是平均桶大小。
阅读更多内容美国国旗排序优化。
阅读Engineering Radix Sort (1993)，论文中对两种算法进行了实验比较。
美国国旗排序的 Java 实现。
美国国旗排序比键索引计数基数排序复杂得多。而不是使用长度为N的辅助数组来存储排序后的结果然后写回原数组。它通过计算出的偏移量直接写回原始数组。 对于它写回的每个项目，原始数组中受影响的项目需要首先写入其最终位置，而该过程可能会影响更多项目，您需要循环写回它们。 参考
AmericanFlagSort.java