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

在C++中，可以编写一个名为`sort_odd_even`的函数，使用两个指针从两端向中间遍历数组，同时检查并交换需要的位置，使得左侧元素都是奇数，右侧元素都是偶数。这个过程不需要额外的数据结构，只需要原地操作，所以时间复杂度是线性的O(n)。

#include <iostream>

void sort_odd_even(int arr[], int n) {
    if (n <= 1) return; // 如果数组长度小于等于1，直接返回

    // 初始化两个指针，一个指向数组开头，另一个指向结尾
    int left = 0, right = n - 1;

    while (left < right) {
        // 只要左指针所指位置的元素是偶数，则移动到右端
        while (arr[left] % 2 == 0 && left < right) {
            left++; // 左指针向右移动一位
        }
        // 只要右指针所指位置的元素是奇数，则移动到左端
        while (arr[right] % 2 != 0 && left < right) {
            right--; // 右指针向左移动一位
        }

        // 如果此时左、右指针未相遇（即两者都有待处理），则交换它们指向的元素
        if (left < right) {
            std::swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
}

// 测试函数
int main() {
    int arr[] = {4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort_odd_even(arr, n);
    
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "\n";

    return 0;
}

在这个示例中，`sort_odd_even`函数首先检查数组是否过短，然后通过两个指针分别寻找并交换奇偶数字，直到左指针超过右指针或二者都到达中间位置。