一个和桶排序相关的问题，整理水果问题

liangbch

这个问题来自我的一个桶排序算法问题。为了便于描述，我们用水果做比喻。
现有n个颜色不同的盒子，n种颜色不同的水果，每个盒子恰好能够装满与其颜色相同的水果。各个盒子的编号为1，2，3，..n, 相应的这个盒子的颜色代号也为1，2，3..n.   现在所有的水果混在一起，装满了n个盒子(也就是说，每个盒子有许多种颜色不同的水果）。现在需要将水果各就各位。步骤如下：

1. 从第1盒子开始，对其中的水果进行整理，挑出颜色颜色代号不等于1的水果放在备用盒子中，等于1的水果不动。。

2. 接着其他盒子，为便于描述，定义当前的盒子为i号。对于i号盒子的某个水果，假定其颜色代号为x,
则，如果x 等于i，这个水果保留不动，
    如果x 小于i, 将这个水果放在第x号盒子，容易看出，此时x号盒子一定有空间。
    如果x 大于i, 将这个水果放在备用盒子。

3. 当所有的盒子中的水果都整理完毕后，再整理备用盒子中的水果，根据其颜色号，放入相应的盒子。

问题，备用盒子的容量至少等于所有盒子容量的多少时，可以按此方法，整理水果。

我得到的一个结论是60%，但是我不知道对错，也无法证明。谁能给出正确的结论和证明过程。

liangbch

补充一点，所有的水果都一样大。

gxqcn

感觉有点像玩“空挡接龙”。

问一下：
各种水果是一样多吗？盒子一样大吗？
水果存取无序吗？（即：可从盒子任意位置取放）

我的理解是：
各种水果可能不一样多（按题意，对应的盒子也不一样大），
水果可存取无序（毕竟是“盒子”，而不是狭长的“小抽屉”）。

应该没错吧？

liangbch

本来这个问题是解决桶排序问题的，对于桶排序，数据（水果）是可以任意存取的。但是我又想近可能的少用辅助存储空间，才提出这个问题。当时没有解决。昨天在公交车上站了大约10几分钟。突然想明白了，应该是辅助盒子的容量和所有盒子的容量一样大，才能解决任意分布的水果的整理问题。我们可以举出这样一个例子来说明一下。
  假设所有的盒子都一样大（即每种颜色的水果都一样多），共有n个盒子，对于前n-1个盒子，第i个盒子中的所有水果的颜色代号都是i+1,第n个盒子中的水果的颜色代号是1.按照整理水果的规则，在整理前n-1个盒子是，需要将所有水果放入备用盒子，因此备用盒子的大小至少为总容量的n-1/n, 当n趋于无穷大时，备用盒子所需容量的趋于100%。

gxqcn

这个构造作得蛮好的。

无心人

假设第一个盒子有1个1号的，1个2号的，8个其他的
同样道理第二个也是

假设有10个盒子

我们可以证明，这么假设是合理的
那整理2号时，将需要16个空间，对不对？

无心人

所以，你的辅助空间将很大
呵呵

liangbch

原帖由 无心人 于 2008-9-13 18:53 发表
假设第一个盒子有1个1号的，1个2号的，8个其他的
同样道理第二个也是

假设有10个盒子

我们可以证明，这么假设是合理的
那整理2号时，将需要16个空间，对不对？

1.不太明白你在6#的描述。
2.关于辅助空间的最大值，我在4#已经得出结论，即所需的辅助空间的最大尺寸等于原始待排序的数据的尺寸。

无心人

我是以具体例子说明
你这么做辅助空间将很大

liangbch

不错，辅助空间是很大，这已经不满足我最初提出的条件。但是到目前为止，很难想出，占用空间少并且速度又快的算法。