深圳市龙岗区做网站的公司/今日国际新闻

    题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

   1、 我的解法代码：

class Solution {
public:void reOrderArray(vector<int> &array) {//if(array == NULL)//return ;for(decltype(array.size()) i = 0;i < array.size();++i)  // 每一个数都要遍历，所以是 size()次{for(decltype(array.size())j = array.size()-1 ;j>i;j--){if ((array[j] %2 ==1) &&(array[j-1] %2 == 0))swap(array[j],array[j-1]);}}}
};

    分析：比如数字1 2 3 4 5 6 7 8，要先遍历一下，然后调整数字的顺序。遍历的话，肯定要循环 array.size()次。如果要调换顺序的话，得从后往前调整，因为偶数需要不停地往后调整。我这种解法代码简洁，但是时间复杂度很高，为 O（n^2）.但是好处是不需要额外的辅助空间。

    2、《剑指offer》上的解法 P105页

    剑指offer一书上，特别强调了程序的可扩展性。参考书吧。但是大体上和我的解法差不多，有两点不同：

    （1）、判断奇偶数，是将该数和 0x1进行“与”运算，这样，利用位运算，确实比取余效率要高。

    （2）、书上使用的是指针的解法，因为形参给的就是指针。而牛客网上这道编程题的形参是 vector 的引用

    3、时间复杂度O（n）,空间复杂度为O（n）的解法

    思路：可以额外申请一个数组，把原来数组里面的元素遍历一遍，如果是奇数，就放到数组中。再把原来的数组遍历一遍，如果是偶数就放到数组中。时间复杂度为O（n）,而且还不用排序的思想。

    代码：

class Solution {
public:void reOrderArray(vector<int> &array) {vector<int> result;for(decltype(array.size())i = 0;i < array.size();++i)if(array[i]%2 == 1)result.push_back(array[i]);for(decltype(array.size())i = 0;i < array.size();++i)if(array[i] %2 == 0)result.push_back(array[i]);array = result;}
};

    4、利用c++ 中 STL 中的 stable_partition()函数

    这个函数的功能是，如果isOK是真的，放到数组的前面，如果是假的，放到数组的后面。

    代码：

bool isOK(int n){return ((n & 1) == 1);}
class Solution {
public:void reOrderArray(vector<int> &array) {stable_partition(array.begin(),array.end(),isOK);}
};

    其中，源码为：

template <class BidirectionalIterator, class UnaryPredicate>  BidirectionalIterator partition (BidirectionalIterator first,  BidirectionalIterator last, UnaryPredicate pred)  
{  while (first!=last) {  while (pred(*first)) {  ++first;  if (first==last) return first;  }  do {  --last;  if (first==last) return first;  } while (!pred(*last));  swap (*first,*last);  ++first;  }  return first;