我正在尝试实施美式桶排序。Wiki 说“首先计算将落入每个箱子的对象数量，然后将每个对象放入其桶中。”
在第二阶段，将对象放置在适当的桶中时，我需要使用辅助数组吗？有没有办法通过在线性时间内交换数组元素来做到这一点？
问问题
1491 次
1 回答
3
假设您的意思是http://en.wikipedia.org/wiki/American_flag_sort，那么正如文章在顶部指出的那样，您可以就地运行它（尽管这不是一个稳定的排序）。主要思想是有一个指向第一个未读入的项目的指针，最初为 0，以及一个临时变量来保存一个项目。
作为第一步，您查看指针并拿起它指向的项目。现在您可以使用索引将其放置到位。除非它的位置是您最初读取的位置，否则您将要覆盖另一个项目，因此您将拾取的项目与您将覆盖的项目交换，并且您现在持有不同的临时项目 - 并抬头看看它应该去哪里继续。
最终，您已将某些内容放入您从中读取的位置，因此您可以增加读取指针，跳过您已经写入已排序项目的区域，拿起不同的项目，并继续进行，直到所有内容都已排序。
于 2011-11-25T05:29:06.350 回答