解法二

很多人其实最先想到的解法可能是，创建一个新的数组，从头扫描，遇到偶数放后边，遇到奇数放前边。扫描结束后，再将数组内容拷贝到原数组，这样整个时间复杂度为(n）,而空间复杂度也为O(n)，这样的方法实现简单，也不容易出错。C语言代码实现如下：

//reorder1.c
void reorder(int arr[],int len)
{
    if(NULL == arr || 0 == len)
        return;
    /*记录奇偶的数量*/
    int oddNum = 0;
    int evenNum = 0;
    int loop = 0;
    /*创建一个新的数组*/
    int *temp = malloc(len * sizeof(int));
    if(NULL == temp)
    {
        printf("malloc memory failed\n");
        return;
    }
    /*拷贝数组，并遍历*/
    memcpy(temp,arr,sizeof(int)*len);
    for(;loop < len;loop++)
    {
        /*偶数放到数组末尾*/
        if(0 == (temp[loop] & 1))
        {
            arr[len-1-evenNum] = temp[loop];
            evenNum++;
        }
        /*奇数放到数组末尾*/
        else
        {
            arr[oddNum] = temp[loop];
            oddNum++;
        }
    }
    free(temp);
}

解法三

还记得我们之前介绍过的《快速排序优化详解》吗？快速排序中，有一个分区操作，是将整个数组大于等于基准的部分放右边，而小于等于基准的部分放左边，即根据基准，将数组一分为二。其实在这里，同样可以参考这个思路，只不过跟基准比大小，变成了判断是奇还是偶。
这里简单描述一下该思路，更多细节可以参考《快速排序优化详解》中如何将元素移动到基准两侧一节：

• 定义下标i和j，分别从开头和结尾开始扫描
• 当i遇到偶数时，停止扫描
• 当j遇到奇数时，停止扫描
• 此时交换i和j位置的值
• 继续前面的操作，直到i和j交错或相等

举个例子，假设有数据1,2,3,4,5,6,7,8：

i和j继续扫描，i遇到2停止，j遇到5停止，交换两处的值：