面试题21：调整数组顺序使奇数在偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

思路一：剑指offer的思路，这种思路无法保证奇数之间以及偶数之间的相对位置不变，使用两个指针来解决，具体如下思维导图

21 调整数组顺序使奇数位于偶数前面.png

思路一代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if len(array)<=0:
            return
        begin = 0
        end = len(array)-1
        while(begin<end):
            while (begin<end) and (self.IsOdd(array[begin])):   #首指针是奇数
                begin+=1
            while (begin<end) and (not self.IsOdd(array[end])):    #尾指针是偶数
                end-=1
            if begin<end:
                temp = array[begin]
                array[begin] = array[end]
                array[end] = temp
        return array
        def IsOdd(self,num):  #是否是奇数
            return num&0x01==1

思路二：
（这种思路可以保证奇数与奇数以及偶数与偶数之间的相对顺序不变）需要将奇数和偶数分别加入两个列表，最后再将两个数组组合即可，思路较为简单

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        #思路2：需要额外的列表
        if array is None or len(array)==0:
            return []
        
        odd_list =[]
        even_list =[]
        for num in array:
            if num&0x01==1:
                odd_list.append(num)
            else:
                even_list.append(num)
        return odd_list+even_list

代码提交结果：

提交结果