美国国旗分类优化 [英] american flag sort optimization

问题描述

我正在尝试实施American Bucket Sort。 Wiki表示：首先计算将落入每个容器中的对象的数量，其次将每个对象放入其存储桶中。

I am trying to implement American Bucket Sort. Wiki says "first to count the number of objects that will fall in each bin, and second to place each object in its bucket."

在第二阶段，放置对象时在适当的存储桶中，是否需要使用辅助阵列？有没有办法通过在线性时间内交换数组元素来做到这一点？

In second phase, when placing objects in proper buckets, Do I need to use auxiliary array? Is there a way to do this by swapping array elements in linear time?

推荐答案

假设您的意思是 http://en.wikipedia.org/wiki/American_flag_sort ，然后如文章顶部所示，您可以就地运行此命令（尽管这不是稳定的排序）。主要思想是要有一个指针，指向未读入的第一个项目，最初是0，还有一个临时变量来保存一个项目。

Assuming you mean http://en.wikipedia.org/wiki/American_flag_sort, then as the article points out at the top, you can run this in-place (although then this is not a stable sort). The main idea is to have a pointer to the first item not read in, initially 0, and a temporary variable to hold one item.

作为第一步，您要看指针并拿起它指向的项目。现在，您可以使用索引来放置它。除非它的位置是您最初读取的位置，否则您将要覆盖另一个项目，因此您将要拾取的项目与要覆盖的项目交换，现在您持有另一个临时项目-抬头看一看

As the first step you look at the pointer and pick up the item it points it. Now you can use the indexes to put it in place. Unless its place is the position you originally read from, you are about to overwrite another item, so you swap the item you have picked up with the item you would overwrite, and you are now holding a different temporary item - and look up to see where it should go and carry on.

最终，您已经将一些内容放到了要读取的位置，因此您可以增加读取指针，跳过已经存在的区域编写已排序的项目，拿起另一个项目，然后继续进行直到所有项目都已排序。

Eventually you have put something into the place you read from, so you can increment the read pointer, skipping over areas where you have already written sorted items, pick up a different item, and carry on until everything is sorted.

这篇关于美国国旗分类优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！