第一反应使用双指针

时间复杂度O(2N)，空间复杂度O(N)，包含返回数组。

int *reOrderArray( int *array, int arrayLen, int *returnSize ) {
    int *returnAry = NULL, left = 0, right = 0;

    returnSize[0] = 0;
    if( array == NULL || arrayLen < 1 ) {
        return NULL;
    }

    returnAry = (int *)malloc( arrayLen * sizeof(*returnAry) );

    // 统计奇数的数量, 记为 count2.
    // 这样做可以划分出存储偶数和存储奇数的下标范围,
    // [0, count2 - 1]范围存储奇数, [count2, arrayLen - 1]范围存储偶数.
    for( int i = 0; i < arrayLen; ++i ) {
        right += (array[i] & 1) ? 1 : 0;
    }
    for( int i = 0; i < arrayLen; ++i ) {
        returnAry[(array[i] & 1) ? (left++) : (right++)] = array[i];
    }
    returnSize[0] = arrayLen;

    return returnAry;
}