剑指offer 13. 调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路
思路1：开辟新的数组，遍历原数组将奇数偶数分别放在新的空间里，最后合并。时间复杂度O(n),开辟了额外的数组空间,空间复杂度O(n)。
思路2：用while来遍历，遇到偶数删除这个偶数，并将其向数组的末尾插入。时间复杂度O(n),没有开辟额外的数组空间，空间复杂度O(1)。勘误：实际上pop(index)的时间复杂度是O(n)，删除元素时后面的元素往前移动，总的时间复杂度接近O(n^2)

代码实现
思路1：暴力解

class Solution:
    def reOrderArray(self, array):
        # write code here
        # 暴力解，时间复杂度O(n),开辟了额外的数组空间
        odd = []
        even = []
        for i in array:
            if i%2 == 1:
                odd.append(i)
            else:
                even.append(i)
        array = odd + even
        return array

思路2：将偶数尾插入数组

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        # 没有额外的数组空间。
        # 实际上pop(index)的时间复杂度是O(n)，删除元素时后面的元素往前移动，总的时间复杂度接近O(n^2)
        lenth = len(array)
        move = 0
        index = 0
        while(lenth - move - index > 0):
            if array[index]%2 == 0:
                temp = array.pop(index)
                array.append(temp)
                move += 1
                index -= 1
            index += 1
        return array

能力有限，欢迎各位大佬批评指点，交流是进步的阶梯。