我正在尝试实现美式桶排序。维基百科说：“首先计算每个垃圾箱中掉落的物体数量，然后将每个物体放入其桶中。”
第二阶段，将对象放入适当的桶中时，是否需要使用辅助数组？有没有办法通过在线性时间内交换数组元素来做到这一点？
假设你的意思是http://en.wikipedia.org/wiki/American_flag_sort，然后正如文章在顶部指出的那样，您可以就地运行它（尽管这不是一个稳定的排序）。主要思想是有一个指向第一个未读入的项目的指针（最初为 0）和一个临时变量来保存一个项目。
第一步，您查看指针并拿起它指向的项目。现在您可以使用索引将其放置到位。除非它的位置是您最初读取的位置，否则您将要覆盖另一个项目，因此您将拾取的项目与您要覆盖的项目交换，并且您现在持有一个不同的临时项目 - 抬头看看它应该去哪里并继续下去。
最终，您已将某些内容放入读取的位置，因此您可以增加读取指针，跳过已写入排序项目的区域，拾取不同的项目，然后继续，直到所有内容都排序完毕。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
