【答案解析】给定一个存放整数的数组，如何重新排列数组使得数组左边为奇数，右边为偶数?要求：空间复杂度为O(1)，时间复杂度为O(N)。
类似快速排序的处理。可以用两个指针分别指向数组的头和尾，头指针正向遍历数组，找到第一个偶数，尾指针逆向遍历数组，找到第一个奇数，交换两个指针指向的数字，然后两指针沿着相应的方向继续向前移动。重复上述步骤，直到头指针大于等于尾指针为止。具体实现如下：
#include＜iostream＞
using namespace std;
void Swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
void ReverseArray(int arr[],int len)
{
int begin=0;
int end =len-1;
while(begin＜end)
{
while(arr[begin]%2==1 && end＞begin)
{
++begin;
}
while(arr[end]%2==0 && end＞begin)
{
--end;
}
Swap(arr[begin],arr[end]);
}
}
int main()
{
int array[]={1,23,2,34,21,45,26,22,41,66,74,91,17,64};
int len=sizeof(array)/sizeof(array[0]);
int i;
printf("原数组为:");
for(i=0;i＜len;i++)
printf("%d",array[i]);
printf("/n");
ReverseArray(array,len);
printf("经过变换后的数组为:");
for(i=0;i＜len;i++)
printf("%d",array[i]);
printf("/n");
return 0;
}
程序输出结果：
原数组为：1 23 2 34 21 45 26 22 41 66 74 91 17 64
经过变换后的数组为：1 23 17 91 21 45 41 22 26 66 74 34 2 64