arrays - 优化算法安排一个数组，其中偶数索引的项目在数组的左侧，奇数索引的项目在数组的右侧

Question

要求:使用递归，数组大小为偶数。

例如:

0...1...2...3...4...5(索引顺序)

a...b...c...d...e...f(先排列后排列)

a...c...e...b...d...f(排列后排列)

---

0……1……2……3……4……5……6…… ..7(索引顺序)

a1....b1....a2....b2....a3....b3....a4....b4 (array before arrange)

a1....a2....a3....a4....b1....b2....b3....b4(排列后排列)

---

如果我们不关心优化问题看起来很容易解决，我们可以使用临时数组或使用递归结合循环来移动项目......我认为这种方式不是最好的解决方案......我尝试使用递归结合交换操作，不使用循环......但我失败了。

希望有人建议我解决问题的想法，感谢任何帮助

Answer 1

首先，让我提一下，最佳解决方案取决于数组的大小(占用了多少元素)假设这在内存中，这意味着数组大小受到限制，您可以通过快速循环来解决复杂性O(n) 就像这样。设数组为 N，N 中元素的个数为 x。

• 获取所有奇数元素的起始索引 = x/2(如果 x 是偶数)或 (x+1)/2
• 让那个索引是一个
• 让偶数元素从 b 开始。让 b = 0
• 创建名为 T 的输出数组
• while start = 0 但小于 x，INCR 和 BEGIN
• 如果start是偶数，将N(start)处的元素放入T(b++)
• 如果start是奇数，将N(start)处的元素放入T(a++)

数组插入和查找被接受为 O(1)。

操作是

1. 确定当前索引，你不能避免检查数组中的每个索引。
2. 您无法避免生成输出，但删除元素、检索值并将其放置在正确位置的计算成本更高。更容易插入内存中已分配的空间。

您确实可以选择运行并发 for 循环，这会加快速度，但我想这超出了您的期望。