写一个c++函数，已知数组中的元素为整形，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)

在C++中，你可以编写一个名为`rearrangeArray`的函数，该函数采用分治策略并利用双指针技巧来达到目标。以下是这个算法的一个实现：

#include <vector>

void rearrangeArray(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        // 找到第一个奇数
        while (nums[left] % 2 == 0 && left < right) {
            left++;
        }
        
        // 找到第一个偶数
        while (nums[right] % 2 != 0 && left < right) {
            right--;
        }

        // 如果左指针小于右指针，交换两个位置的元素
        if (left < right) {
            std::swap(nums[left], nums[right]);
        }
        // 左右移动指针
        left++;  // 左指针向右移动一位偶数
        right--; // 右指针向左移动一位奇数
    }
}

// 示例
int main() {
    std::vector<int> arr = {4, 2, 5, 7, 1, 8, 6};
    rearrangeArray(arr);
    for (const auto& num : arr) {
        std::cout << num << " ";
    }
    return 0;
}