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

这道题目可以使用双指针来实现，具体步骤如下：

1. 定义两个指针 i 和 j，分别指向序列的第一个位置和最后一个位置。

2. 当 i 小于 j 时，循环执行以下步骤：

- 如果 a[i] 是偶数，则将 i 加 1，指向下一个位置。

- 如果 a[j] 是奇数，则将 j 减 1，指向上一个位置。

- 如果 a[i] 是奇数，a[j] 是偶数，且 i 小于 j，则交换 a[i] 和 a[j]。

3. 循环结束后，序列中偶数在前，奇数在后。

下面是使用 C 语言实现的代码：

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int a[], int n) {
    int i = 0, j = n - 1;

    while (i < j) {
        if (a[i] % 2 == 0) {
            i++;
        } else if (a[j] % 2 == 1) {
            j--;
        } else {
            swap(&a[i], &a[j]);
            i++;
            j--;
        }
    }
}

int main() {
    int t, n, i, j;

    scanf("%d", &t);  // 读入测试次数

    for (i = 0; i < t; i++) {
        scanf("%d", &n);  // 读入整数个数
        int a[n];
        for (j = 0; j < n; j++) {
            scanf("%d", &a[j]);  // 读入整数
        }
        sort(a, n);  // 调整数字位置
        for (j = 0; j < n; j++) {
            printf("%d ", a[j]);  // 输出整数序列
        }
        printf("\n");
    }

    return 0;
}

输入样例：

2
8 1 2 3 4 5 6 7 8
10 1 2 3 4 5 6 7 8 9 10

输出样例：

2 8 6 4 5 3 7 1 
2 4 6 8 10 1 3 5 7 9