c++ - 如何在时间和空间复杂度的限制下对偶数和奇数进行交替排序？(C/C++)

Question

给定一个整数数组

int numbers[8]={1, 3, 5, 7, 8, 6, 4, 2};

前面数组的一半是奇数，其余(等量数)是偶数。奇数部分按升序排列，偶数部分按降序排列。排序后，数字的顺序不能改变。

如何在时间复杂度小于O(n^2) 和空间复杂度O(1) 的情况下对它们进行交替排序？

对于这个例子，结果将是:{1,8,3,6,5,4,7,2};

我不能使用外部数组存储，但可以接受临时变量。

我试过用两个指针(oddPtr, evenPtr)分别指向奇数和偶数，移动evenPtr将偶数插入奇数的中间数字。(如插入排序)
但它需要 O(n^2)。

已更新

Answer 1

根据 Dukeling 的评论，我意识到我提出的解决方案实际上不是线性的，而是线性的，甚至更糟 - 您无法控制它是否需要额外的内存。在我的第二个想法中，我意识到你对数组了解很多，可以实现一个更具体但可能更简单的解决方案。

我假设数组中的所有值都是正数。我需要这个以便我可以使用负值作为一种“已处理”标志。我的想法如下 - 从左到右遍历数组。对于每个元素，如果它已经被处理(即它的值为负)，只需继续下一个。否则你将有一个常量公式，其中该元素应该位于的位置:

• 如果值为奇数且其索引为 i，则应移至 i*2
• 如果值为偶数且其索引为 i，则应移至 (i - n/2)*2 + 1

将这个值存储到一个临时值中，并使数组当前索引处的值成为0。现在直到我们“手头”的值不为零的位置，将它与我们应该保留的值交换根据上面的公式放置它。此外，当您将值放在手边时，将其取反以“将其标记为已处理”。现在我们有了一个“手头”的新值，我们再次根据上面的公式计算它应该去的地方。我们继续移动值，直到我们“手头”的值应该到达 0 的位置。稍加思考，您就可以证明手头永远不会有负值(“已处理”)，最终您将结束在数组的空白处。

处理完所有值后，在数组上迭代一次以取反所有值，您将获得所需的数组。我描述的算法的复杂性是线性的——每个值不会超过一次“手头”，你将迭代它不超过一次。