我正在尝试实现美式桶排序。 Wiki 说“首先要计算落入每个容器中的对象数量，然后将每个对象放入其桶中。”
第二阶段，将对象放入适当的桶中时，是否需要使用辅助数组？有没有办法通过在线性时间内交换数组元素来做到这一点？
最佳答案
假设您的意思是 http://en.wikipedia.org/wiki/American_flag_sort ，然后正如文章顶部指出的那样，您可以就地运行它(尽管这不是一种稳定的排序)。主要思想是有一个指针指向第一个未读入的项目，最初为 0，以及一个临时变量来保存一个项目。
作为第一步，您查看指针并拿起它指向的项目。现在您可以使用索引将其放置到位。除非它的位置是你最初阅读的位置，否则你将要覆盖另一个项目，所以你将你拿起的项目与你要覆盖的项目交换，你现在拿着一个不同的临时项目 - 抬头看看它应该去哪里继续。
最终，您已将一些内容放入您读取的位置，因此您可以递增读取指针，跳过您已经写入已排序项目的区域，选择不同的项目，并继续直到所有内容都已排序。
关于algorithm - 美国国旗排序优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8262797/