问答题 试设计一个算法,将A[0…n-1]中所有奇数移到偶数之前。要求不另增加存储空间,且时间复杂度为O(n)。
【正确答案】i从左向右遍历,指向A左边的一个偶数,j从右向左遍历,指向A右边的一个奇数,然后将A[i]与A[j]交换,如此循环直到i大于等于j。代码如下: void move(int A[],int n) { int i=0,j=n-1,temp; while(i<j) { while(A[i]*2==1 && i<j) //A[i]为一个偶数 ++i; while(A[j]%2==0 && i<j) //A[j]为一个奇数 --j; if(i<j) //i[i]与A[j]交换 { temp=A[i]; A[i]=A[j]; A[j]=temp; ++i;--j; } } }
【答案解析】