整型数组A[n]中的元素调整为左右两部分，其中左边所有元素为奇数，右边所有元素为偶数。时间复杂度为O(n)。

可以使用双指针的方法来实现这个问题，一个指针从数组的左端开始向右移动，另一个指针从数组的右端开始向左移动。当左指针指向偶数时，右指针指向奇数时，交换这两个指针所指向的元素。这样，经过一次遍历后，数组的左边部分将全部是奇数，右边部分全部是偶数。

以下是实现该算法的C++代码：

#include <iostream>
#include <vector>

void rearrangeArray(std::vector<int>& A) {
    int left = 0, right = A.size() - 1;
    while (left < right) {
        // 从左向右找到第一个偶数
        while (left < right && A[left] % 2 != 0) {
            left++;
        }
        // 从右向左找到第一个奇数
        while (left < right && A[right] % 2 == 0) {
            right--;
        }
        // 交换这两个元素
        if (left < right) {
            std::swap(A[left], A[right]);
        }
    }
}

int main() {
    std::vector<int> A = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    rearrangeArray(A);
    
    for (int num : A) {
        std::cout << num << " ";
    }
    
    return 0;
}

运行上述代码后，数组 `A` 的元素将被重新排列，奇数元素位于左边，偶数元素位于右边。