将数组C[1:n]中所有奇数移到偶数之前，要求时间复杂度为O(n)

Question

将数组C[1:n]中所有奇数移到偶数之前，要求时间复杂度为O(n)

Answer 1

快速排序的思想！

int *rev(int *a, int n)
{
int *p, *q;
int temp;
p = a;
q = a + n - 1;
while(p < q)
{
while((*p)%2) p++;
while(!((*q)%2)) q--;
if(p < q)
{
temp = *p;
*p = *q;
*q = temp;
p++;
q--;
}
}
return a;
}本回答被提问者采纳

Answer 2

void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void shift(int a[], int n)
{
int first_not_odd = -1;
int i;
for ( i=0; i<n; ++i)
{
if ( a[i] % 2 )
swap( &a[i], &a[ ++ first_not_odd ]);
}
}
int main()

{
int a[10];
shift(a, 10);
}

参考资料：我刚才没登陆~~呵呵

Answer 3

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

void shift(int a[], int n)
{
int first_not_odd = -1;
int i;
for ( i=0; i<n; ++i)
{
if ( a[i] % 2 )
swap( &a[i], &a[ ++ first_not_odd ]);
}
}

Answer 4

#include<iostream>
#include<iterator>
#include<algorithm>
inline bool isodd(int i){return i%2 != 0;}

int main()
{
int a[]={1,2,3,4,5,6,7,8,9};
int b[sizeof a/sizeof a[0]];
std::partition(a,a+sizeof a/sizeof a[0],isodd);
std::copy(a,a+sizeof a/sizeof a[0],b);
std::copy(b,b+sizeof b/sizeof b[0],std::ostream_iterator<int>(std::cout," "));
system("pause");
}