D. 数组奇偶排序（数组） 题目描述 输入n，输入n个整数。调整数字位置使得偶数在序列的前半部分，奇数在序列的后半部分。 注：自己根据样例输入、输出找到算法。 要求算法的时间复杂度为O(n)。

可以使用双指针法来实现时间复杂度为O(n)的奇偶排序算法。

具体步骤如下：

1. 定义两个指针，一个指向序列的开头，一个指向序列的结尾。

2. 当左指针指向的数是偶数时，左指针向右移动一位；当右指针指向的数是奇数时，右指针向左移动一位。

3. 当左指针指向的数是奇数，右指针指向的数是偶数时，交换左右指针所指向的数，并将左指针向右移动一位，右指针向左移动一位。

4. 重复步骤2-3，直到左指针和右指针相遇。

以下是实现该算法的 Python 代码：

n = int(input())
nums = list(map(int, input().split()))

left, right = 0, n - 1

while left < right:
    if nums[left] % 2 == 0:
        left += 1
    elif nums[right] % 2 == 1:
        right -= 1
    else:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

print(' '.join(map(str, nums)))