对给定数组按奇偶性划分，不改变相对顺序

问题描述

给定一个数组，比如 arr = { 1, 3, 1, 4, 1, 5, 2, 0}，对该数组进行整理，使得所有奇数都在前面，，所有的偶数都在后面，且保证所有奇数的相对顺序不改变，所有偶数的相对顺序不改变。

问题解决Solution1：T(n) = O(n^2), S(n) = O(1)

利用冒泡排序的思想，对数组进行整理即可。 思想：扫描数组，针对每个发现的奇数，都利用冒泡技术，往前移动该奇数，直到碰见了其他奇数。

Solution2：T(n) = O(n), S(n) = O(n)

如果空间复杂度达到S(n) = O(n)，那么其实很简单：

Solution3：T(n) = O(n log n)，S(n) = O(1)

针对数组利用分而治之的思想：

对调的API：

void swap(vector<int> &arr, int i, int j, int k) {reverse(arr, i, j);reverse(arr, j+1, k);reverse(arr, i, k);}

因此时间复杂度是： T(n) = T(n/2) + T(n/2) + O(n), 因此T(n) = O(n log n)

艰苦能磨练人的意志。