题解 | #调整数组顺序使奇数位于偶数前面#

描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
输入：[1,2,3,4]
返回值：[1,3,2,4]

输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]
方法一：分别新建两个数组，一个用来按原来的相对位置存放奇数，一个存放偶数，最后将两组数据进行奇数在前，偶数在后的顺序进行合并。
vector<int> reOrderArray(vector<int>& array) {
// write code here
vector<int>B;//存放奇数
vector<int>C;//存放偶数
vector<int>D;//存放最后排列好的数据
for(int i = 0; i < array.size(); i++)
{
if(array[i] % 2 == 0)
{
C.push_back(array[i]);
}
else{
B.push_back(array[i]);
}
}
for(int i = 0; i < B.size(); i++)
{
D.push_back(B[i]);
}
for(int i = 0; i < C.size(); i++)
{
D.push_back(C[i]);
}
return D;
}
时间复杂度：O(n)
空间复杂度：O(n)
方法二：利用冒泡的思想，碰到奇数向前移动。
vector<int> reOrderArray(vector<int>& array) {
// write code here
int oddIndex = -1;
for(int i = 0; i < array.size(); i++)
{
if(array[i] % 2 == 1)
{
oddIndex++;
int odd = array[i];
for(int j = i; j > oddIndex; j--)
{
array[j] = array[j-1];
}
array[oddIndex] = odd;
}
}
return array;
}
时间复杂度：O(n^2)
空间复杂度：O(1)
方法二不如方法一好，优先考虑时间复杂度。方法二学习到了一种保存数据的方法，先将数据赋值给新定义的变量进行保存，然后再对剩余的数据进行操作。</int></int></int></int></int></int></int>