能否在C++中以O(N)时间复杂度实现指定数组重排算法？

问题描述 #

我正在尝试用C实现一个函数，接收整数数组并原地返回按以下规则排序后的数组（我是C和计算机科学领域的初学者）：

• 所有奇数排在偶数之前
• 奇数保持原有相对顺序
• 偶数按原有相对顺序逆序排列

示例：输入arr = [5, 2, 11, 7, 6, 4]，输出应为[5, 11, 7, 4, 6, 2]。

现有解法及问题 #

我想到的解法能正常运行，但最坏情况下时间复杂度为O(n²)，步骤如下：

• 若数组第i个元素是偶数，则与数组中尚未交换过的最后一个偶数交换
• 若数组第i个元素是奇数，则不断与第i-1个元素交换，直到第i-1个元素是奇数或到达数组开头
• 处理下一个元素

疑问 #

我难以构思O(n)时间复杂度的实现思路，想不到单次遍历就能把所有元素放到对应位置的方法，想到的算法都需要遍历加某种排序。这种情况下O(n)算法是否可行？

注：我知道可以通过创建新数组并按规则复制元素来实现，但这不够有趣，我希望深入理解高效的原地算法实现。

解答 #

可以实现O(n)时间复杂度的原地解法，给你几个关键提示，你可以自行尝试推导代码：

1. 按顺序归集奇数，保留相对顺序

   • 用一个指针odd_pos标记当前奇数应该放置的位置（初始为0），遍历整个数组：
     • 遇到奇数时，将它移动到odd_pos的位置，然后odd_pos向后移动一位；
     • 遇到偶数则跳过，继续遍历。
   • 这一步结束后，数组前odd_pos个元素是所有奇数，且完全保留原有的相对顺序；从odd_pos到数组末尾的元素是所有偶数，保留了原有的相对顺序。

2. 逆序偶数区域

   • 对数组中从odd_pos到末尾的偶数子数组，执行原地逆序操作（比如用双指针，一头一尾交换元素，直到指针相遇）。
   • 逆序后，偶数的顺序就变成了原顺序的倒序，完全符合要求。

这两步的时间复杂度都是O(n)，且只用到了常数级额外空间，满足你的需求。

内容的提问来源于stack exchange，提问作者rlusardi113