已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元 素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。

要实现这个要求，我们可以使用双指针法，一种常见的数组操作技巧。这里有一个简单的C++算法：

#include <vector>

void rearrangeArray(std::vector<int>& A, int n) {
    if (n == 0 || n == 1) return; // 如果数组为空或只有一个元素，无需处理

    int left = 0, right = n - 1; // 定义左指针和右指针
    while (left < right) {
        // 当左指针指向的元素是偶数，右指针指向的元素是奇数时交换
        if (A[left] % 2 == 0 && A[right] % 2 != 0) {
            std::swap(A[left], A[right]);
            left++; // 左指针右移一位
        } else if (A[left] % 2 != 0) { // 只有左指针指向的是奇数
            left++;
        } else { // 只有右指针指向的是偶数
            right--;
        }
    }
}

// 示例用法
int main() {
    std::vector<int> A = {1, 2, 3, 4, 5, 6};
    rearrangeArray(A, A.size());
    for (const auto& num : A) {
        std::cout << num << " ";
    }
    return 0;
}

在这个算法中，我们从两端开始遍历数组，如果发现左端的元素是偶数而右端的元素是奇数，我们就交换它们并同时移动指针。否则，根据当前元素的奇偶性决定只移动左指针（遇到奇数）或右指针（遇到偶数）。当左指针大于等于右指针时，数组就已经按照要求排序了。

时间复杂度分析：由于每个元素只会被访问一次，所以总的时间复杂度是O(n)，其中n是数组的长度。空间复杂度是O(1)，因为我们只使用了几个额外的变量，没有使用与n成比例的额外空间。