鉴于 integer array 喜欢
int numbers[8]={1, 3, 5, 7, 8, 6, 4, 2};
前阵列中的半边是奇数，其余（等量数）是偶数 . 奇数按升序排列，偶数部分按降序排列 . 排序后，数字的顺序不能改变 .
如何以时间复杂度 less 和空间复杂度 O(1) 交替对它们进行排序？
对于此示例，结果将是： {1,8,3,6,5,4,7,2} ;
I can't use external array storage but temporary variables are acceptable.
我试图使用两个指针（ oddPtr, evenPtr ）分别指向奇数和偶数，并移动 evenPtr 将偶数值插入奇数的中间 . （如插入排序）
但它需要 O(n^2) .
UPDATED
1 回答
根据Dukeling的评论，我意识到我提出的解决方案实际上不是线性的，而是线性的，甚至更糟 - 你无法控制它是否需要额外的内存 . 在我的第二个想法中，我意识到你对阵列有很多了解，你可以实现更具体，但可能更简单的解决方案 .
我将假设数组中的所有值都是正数 . 我需要这个，以便我可以使用负值作为“已处理”标志 . 我的想法如下 - 从左到右遍历数组 . 对于每个元素，如果它已被处理（即它的值为负），只需继续下一个元素 . 否则你将有一个常量公式，其中该元素的位置应该是：
如果该值为奇数且其索引为
i，则应移至i*2如果值为偶数且其索引为
i，则应移至(i - n/2)*2 + 1将此值存储到临时值中并将值设置为数组0的当前索引 . 现在直到我们手头的值不为零的位置，将其与保留在我们应该放置的位置的值交换到上面的公式 . 此外，当您将值放在手边时，将其标记为“将其标记为已处理” . 现在我们有一个新的 Value '手头'，我们再次根据上面的公式计算它应该去哪里 . 我们继续移动 Value ，直到我们手边的 Value 应该转到0的位置 . 稍微想一想你可以证明你手头上永远不会有负面（'处理'）值，最终你会最终在阵列的空位 .
处理完所有值后，在数组上迭代一次以取消所有值，您将获得所需的数组 . 我描述的算法的复杂性是线性的 - 每个值不会超过一次“手头”，你将迭代它不超过一次 .