【Hacker News搬运】美国国旗分类

[hackernews]

Title: American flag sort

美国国旗分类

Text:

hn link

Url: https://xlinux.nist.gov/dads/HTML/americanFlagSort.html

美国国旗排序（American flag sort）是一种有效的排序算法，它是基数排序（radix sort）的一种原地（in-place）变体。这种算法通过将项目分配到数百个桶（buckets）中来分布项目。首先，它计算每个桶中的项目数量，然后计算每个桶在数组中的起始位置。最后一步是通过循环排列（permutes）项目，使其到达各自的桶中。由于桶在数组中是有序的，因此没有收集步骤。这个算法的名字来自于最后一步，与荷兰国旗问题（Dutch national flag problem）的类比：高效地将数组划分为许多“条纹”。使用一些效率技术，对于大型字符串集合，它的速度是快速排序（quicksort）的两倍。

更多信息可以在[美国国家标准与技术研究院（NIST）的算法和数据结构词典](https://www.nist.gov/dads/)中找到。该算法的作者是彼得·M·麦克Ilroy（PEB），它是在麦克Ilroy，博斯特和麦克Ilroy的论文中实现的。此外，这种排序算法在每字节排序时特别有效，尤其是使用256个桶时。

这种排序算法的实现细节和参考文献可以在[这里](https://www.semanticscholar.org/paper/Engineering-Radix-Sort-McIlroy-Bostic/3bcf2b6e1f2515d94a2de45cd096b063900fb0f6)找到。如果对算法有任何建议、纠正或评论，可以联系保罗·布莱克（Paul Black）。请注意，这个入口是在2023年1月24日修改的。

Post by: zerojames

Comments:

muti: Visualisation <a href="https://www.youtube.com/watch?v=k1XkZ5ANO64" rel="nofollow">https://www.youtube.com/watch?v=k1XkZ5ANO64</a><p>Wikipedia page <a href="https://en.wikipedia.org/wiki/American_flag_sort" rel="nofollow">https://en.wikipedia.org/wiki/American_flag_sort</a>

muti: 可视化<a href=“https://；&#x2F；www.youtube.com&#x2F！watch？v=k1XkZ5ANO64”rel=“nofollow”>https://&#x2F；www.youtube.com&#x2F；看v=k1XkZ5ANO64</a><p>维基百科页面<a href=“https://；&#x2F；en.Wikipedia.org&#x2F：wiki&#x2F，American_flag_sort”rel=“nofollow”>https://&#x2F；en.wikipedia.org&#x2F；wiki&#x2F；美式_flag_sort</a>

karmakaze: At first I didn't think I'd be interested.<p>> Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.

karmakaze: 一开始我没有；我不认为我；我很感兴趣<p> &gt；使用一些高效技术，对于大型字符串集，它的速度是快速排序的两倍。

re: Looks like there's a Rust implementation: <a href="https://crates.io/crates/afsort" rel="nofollow">https://crates.io/crates/afsort</a><p>> When sorting English words, this implementation seems to be about 40% faster than sort_unstable from the Rust standard library.<p>That's better than I would have expected. It would be interesting to see how it does on other types of string sort problems.

re: 看起来有&#7；s a Rust实现：<a href=“https://；&#x2F；crates.io&#x2F：crates&#x2F！afsort”rel=“nofollow”>https://&#x2F；板条箱.io；板条箱；afsort</a><p>&gt；在对英语单词进行排序时，这种实现似乎比Rust标准库中的sort_instantable快40%左右<p> 那个；It’这比我预想的要好。看看它在其他类型的字符串排序问题上的作用会很有趣。

jdeisenberg: Wondering how this sort would perform with Unicode input (given 256 buckets); specifically what the results would look like.

jdeisenberg: 想知道这种排序在Unicode输入（给定256个桶）时会如何执行；特别是结果会是什么样子。

tomphoolery: Freedom Sort.

tomphoolery: 自由型。