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