Question

已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数

已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。

下面这个符合要求吗？我怎么感觉很麻烦？有没有更简单的？

-------------------

void sortOddEven() {
int n;
int b = 0, c = 0;
printf("请输入数组长度\n");
scanf("%d", &n);
int *A = malloc(sizeof(int) * n);
int *odds = malloc(sizeof(int) * n);
int *evens = malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
printf("请输入各个元素\n");
scanf("%d", &A[i]);
}
for (int i = 0; i < n; i++) {
if (A[i] % 2) {
odds[b++] = A[i];
} else {
evens[c++] = A[i];
}
}
for (int i = 0; i < n; i++) {
A[i] = odds[i];
}
for (int i = 0; i < c; i++) {
A[i + b] = evens[i];
}
for(int i = 0; i < n; i++){
printf("%d\n",A[i]);
}

}

Answer 1

1、首先我们要先设计一下实验，1定义变量2输入变量3判断4输出。

2、 那么我们就要进行写代码了，这里首先要写头文件。

3、然后定义变量，这里定义一个n就可以了。

4、 再次我都要输入n，在前面应该注释一下，提醒自己要输入。

5、然后判断，如果可以被2整除，就是偶数，否则就是奇数。

6、 编译运行就可以显示你输入的数是奇数还是偶数。

Answer 2

int n;
int b = 0, c = 0;
printf("请输入数组长度\n");
scanf("%d", &n);
int *A = malloc(sizeof(int) * n);
int begin = 0, end = n-1;
int temp;
for (int i = 0; i < n; i++) {
printf("请输入各个元素\n");
scanf("%d", &temp);
if(temp%2)A[begin++]=temp;
else A[end--]=temp;
}

Answer 3

直接用一次快排的变形就好了。
按照快排思想，从两边开始，左边遇到偶数就停，右边遇到奇数就停，然后两个都停的时候就交换这两个数字。终止条件是左边的标志位大于右边的标志位。
如果没什么别的要求，也可以再建一个数组，然后遍历原数组，奇数写进去，再遍历一遍，偶数写进去，然后再赋值回去。