算法设计（要求用C++或者C语言描述算法） 已知数组A[n]中的元素是整型，设计算法将其调整为左右两部分，其中左边是奇数，右边是偶数，并要求算法的时间复杂度是O（n）。不用双指针的方法计算

为了将数组A[n]中的元素按照奇数在前、偶数在后的顺序调整，我们可以使用一种叫做“分治”策略，结合两个栈的数据结构来实现。以下是C++的实现方案：

#include <iostream>
#include <stack>

void rearrangeArray(int arr[], int n) {
    stack<int> oddStack;
    stack<int> evenStack;

    // 将所有元素依次压入对应栈中
    for (int i = 0; i < n; ++i) {
        if (arr[i] % 2 == 0) {
            evenStack.push(arr[i]);
        } else {
            oddStack.push(arr[i]);
        }
    }

    // 取出并弹出栈顶元素，交替放入原数组
    int index = 0;
    while (!oddStack.empty() || !evenStack.empty()) {
        if (!oddStack.empty()) {
            arr[index++] = oddStack.top();
            oddStack.pop();
        }
        if (!evenStack.empty()) {
            arr[index++] = evenStack.top();
            evenStack.pop();
        }
    }
}

// 测试代码
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangeArray(arr, n);

    std::cout << "Adjusted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    return 0;
}

这个算法首先将所有的奇数和偶数分别压入两个栈中，然后从两个栈顶取出元素交替放到原数组的位置上。由于每个元素只会进一次栈，所以时间复杂度是O(n)，空间复杂度也是O(n)，因为最坏的情况是所有元素都是奇数或偶数。