Question

一道C数据结构试题

3.设有一维整数数组A,试使用C或C++语言设计算法,将A中所有的奇数排在所有偶数之前｡要求,时间复杂度尽可能地少,结果仍放在A原来的存储空间｡
请高手帮忙详细说明

Answer 1

这是我们数据结构考试的最后一题呵呵,比较简单的说.
我大概说一下当时我的解法.
记得要设两个指针同时从数组的头和尾进行遍历,
从尾部开始,如果是偶数就向前移,直到遇到一个奇数为止.再从头部判断如果是奇数就往后移,直到遇到一个偶数为止.这时交换两个指针的值.直到两个指针指向一起.
空间复杂度为O(1),时间复杂度在O(n)级.
程序如下:

#include<stdio.h>
int main()
{
int a[]={2,33,24,54,56,34,76,76,78,67,65,34,34,23};
int i,j;
for(i=0,j=sizeof(a)/sizeof(int); i != j; )
{
if( a[j] % 2 == 0 && a[i] % 2 == 0 )
{
j--;
continue;
}
else if( a[j] % 2 !=0 && a[i] % 2 != 0 )
{
i++;
continue;
}

else if( a[j] % 2 == 0 && a[i] % 2 != 0 )
{
j--;
i++;
continue;
}
else
{
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
for(i = 0; i < sizeof(a)/sizeof(int); i++ )
{
printf("%d\t", a[i]);
}
}

Answer 2

void fun(int A[],int n)//n为A中元素个数
{
int i=0,j=n-1,t;
while(i<j)
{
if(A[i]%2==0&&A[j]%2!=0)
{
t=A[i];
A[i]=A[j];
A[j]=t;
}
if(A[i]%2!=0)i++;
if(A[j]%2==0)j--;
}
}
时间复杂度为o(n)