题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
python代码
class Solution(object):
def exchange(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if len(nums)==0:
return []
out_1 = []
out_2 = []
for i in nums:
if i%2==0:
out_2.append(i)
else:
out_1.append(i)
return out_1+out_2
上述的方法非常常规，直接遍历数组找奇数和偶数，并使用了额外的空间来储存奇数和偶数，时间复杂度和空间复杂度均为O(n)。
拓展
我们是否可以尝试不使用额外储存空间的前提下完成任务？当然可以，因为这个问题本质上就是元素的交换。
class Solution(object):
def exchange(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if len(nums)==0:
return []
left_p = 0
right_p = len(nums)-1
while True:
while nums[left_p]&1:
left_p+=1
if left_p>=right_p:
return nums
while not nums[right_p]&1:
right_p-=1
if left_p>=right_p:
return nums
nums[left_p],nums[right_p] = nums[right_p],nums[left_p]
上述代码直接在原数组上进行修改，没有使用额外的储存空间。
我们来简要分析一下思路，直接看while True:部分：
n&1用来判断是否为奇数，奇数：n&1=1，偶数n&1=0（只要一个整数的二进制最后一位是1，则一定为奇数，若为0，则是偶数）；while not is_k(nums[left_p]):从数组头部开始找偶数，当遇到偶数时停止；while is_k(nums[right_p]):：从数组尾部开始找奇数，找到奇数时停止；- 交换上述两个位置的元素，然后继续循环，直到它们在数组的某个位置‘碰头’就代表奇数和偶数交换结束。
做到这里，其实大家可能又会想到一种思路，快慢指针（假设两个指针从左侧出发，慢指针指向下一个奇数的位置，快指针往后搜索奇数，遇到奇数就与满指针的元素交换），其实它跟上述的方法均属于双指针法，只不过切入点不同（起始搜索的方向不同），本质思想是一致的。