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

可以使用双指针的方法，一个指针从序列的开头向后遍历，另一个指针从序列的末尾向前遍历。当左指针遇到奇数，右指针遇到偶数时，交换两个指针所指的数字。直到左指针和右指针相遇。

以下是示例代码：

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)))

时间复杂度为 O(n)，因为只需要遍历一次序列。

相关问题

输入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相遇时，序列中所有偶数都已经移动到了前半部分，所有奇数都已经移动到了后半部分。

给定一个长度为n(0<n≤200)的正整数序列，按照以下要求排序： 奇数排在偶数前面； 奇数与偶数各自从小到大排列； 请根据以上要求完成排序，输出排序后的整数序列。 输入格式: 第一行给定一个整数n,第二行给出n个正整数，每个正整数不会超过int所能表示的范围。 输出格式: 输出排序后的整数序列，每行一个整数，共n行。,写出c语言代码

以下是 C 语言实现该题目的代码：

#include <stdio.h>

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

void oddEvenSort(int arr[], int n) {
    int i, j, odd_idx;
    for (i = 0; i < n-1; i++) {
        odd_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] % 2 && arr[j] < arr[odd_idx])
                odd_idx = j;
        if (i != odd_idx)
            swap(&arr[i], &arr[odd_idx]);
    }
    for (i = 0; i < n-1; i++) {
        if (arr[i] % 2 == 0) {
            int min_idx = i;
            for (j = i+1; j < n; j++)
                if (arr[j] % 2 == 0 && arr[j] < arr[min_idx])
                    min_idx = j;
            if (i != min_idx)
                swap(&arr[i], &arr[min_idx]);
        }
    }
}

int main() {
    int n, i;
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    oddEvenSort(arr, n);
    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);
    return 0;
}

其中，`oddEvenSort()` 函数实现了奇数排在偶数前面并且奇数与偶数各自从小到大排列的排序算法。首先，它找到第一个奇数的位置，然后将其与当前位置交换；接着，它对剩下的偶数进行从小到大的选择排序。

时间复杂度为 O(n^2)，但由于数据规模较小，所以可以通过本题。