输入n,输入n个整数。调整数字位置使得偶数在序列的前半部分,奇数在序列的后半部分。 注:自己根据样例输入、输出找到算法。 要求算法的时间复杂度为O(n)。 输入 测试次数t 每组测试数据格式如下: 整数个数

下面是一个基于荷兰国旗问题的算法，可以在O(n)的时间复杂度内完成题目要求：

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>& nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void partition(vector<int>& nums) {
    int even = 0, odd = nums.size() - 1;
    while (even < odd) {
        if (nums[even] % 2 == 0) {
            even++;
        } else {
            swap(nums, even, odd);
            odd--;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        partition(nums);
        for (int i = 0; i < n; i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

对于每组测试数据，我们可以使用荷兰国旗问题的思路，维护两个指针even和odd，初始化时even指向序列第一个位置，odd指向序列最后一个位置。从左到右遍历序列，如果当前位置上的数字为偶数，就将even指针向右移动一位；如果当前位置上的数字为奇数，就将它和odd指针对应的数字交换，并将odd指针向左移动一位。这样，当even和odd相遇时，序列中所有偶数都已经移动到了前半部分，所有奇数都已经移动到了后半部分。