面试12：调整数组顺序使奇数位于偶数前面

【题目】
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
【思路】
由于要保持相对位置不变，故可采用的排序思想为稳定排序。
堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

又结合题目思路，借用快速排序思想，采用一个两个指针pivot和i。
pivot表示在pivot的左边全为奇数，pivot为第一个偶数出现的位置，i表示当前数组位置。
情况1：array[i]为偶数，不用做任何操作
情况2：array[i]为奇数，则array[i]需要到pivot位置，如pivot==i,无需交换，pivot+1；

        pivot +=1

否则，为保持稳定性，依次交换。

                       for j in range(i,pivot,-1):
                           #交换注意深拷贝，浅拷贝
                           b = array[j-1]
                           array[j],array[j-1] = b , array[j]
                       pivot += 1

【代码】

    def reOrderArray(self, array):
        # write code here
        if array == None:
            return
        else:
            pivot = 0 #记录从左到右第一个偶数的位置,pivot左边全为排好序的奇数
            n = len(array)
            for i in range(n):
                if array[i]%2==1:
                    if pivot == i:
                        pivot +=1
                    else:
                        for j in range(i,pivot,-1):
                            #交换注意深拷贝，浅拷贝
                            b = array[j-1]
                            array[j],array[j-1] = b , array[j]
                        pivot += 1
            #为偶数则不动
        return array

【思路2】采用基数排序思想，依次遍历数组，a1存奇数，a2存偶数，将a1和a2拼接在一起即可。

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        a1 = []#存奇数
        a2 = []#存偶数
        for i in range(len(array)):
            if array[i]&1==1:
                a1.append(array[i])
            else:
                a2.append(array[i])
        return a1+a2