描述

这是一篇面对初级coder的题解。
知识点：队列 指针 排序
难度：二星

题解

题目：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
为了优化代码，思考如何判断奇数和偶数效率最高 
if（x&1）
这样应该只用一个指令周期就能完成判断 开始跳转——有对编译原理感兴趣的同学欢迎讨论

方法一：队列

比较直观的想法是用队列把数组复制一份
一个奇数队列一个偶数队列
整理好再放回原队列 

#include <queue>
class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
         queue<int> odd ;
         queue<int> even ;
         for(int i = 0 ; i <array.size() ;i++){ //第一次遍历，存入两个队列
             if(array[i]&1)
                  odd.push(array[i]);
             else
                  even.push(array[i]);
         }
        int len_odd=odd.size();
        int len_even=even.size();
        int i;
         for(i = 0 ; i <len_odd ;i++){//第二次遍历，从奇数队列中存入原数组
             array[i]=odd.front();
             odd.pop();
         }
         for(; i <array.size() ;i++){//第二次遍历，从偶数队列中存入原数组
             array[i]=even.front();
             even.pop();
         }
        return array;
    }
};
<array.size>
</array.size>
显然，这样执行效率不高
运行时间： 13 ms 占用内存：1576K
时间复杂度O(2n)
空间复杂度O(n)

方法二：冒泡排序的思想

利用冒泡排序的思想，找到奇数就排到前面 

class Solution {
public:
    vectorreOrderArray(vector& array) {
        int odd_num=0;//奇数记录
        int cur_num;
        int i,j;
        for(i=0;i<array.size>=odd_num;j--) 
                    array[j]=array[j-1];
                array[odd_num]=cur_num;
                odd_num++;
            }
        }
        return array;
    }
};</array.size>
运行时间： 125 ms 占用内存：1552K

时间复杂度：O(n2)，同冒泡排序

空间复杂度：O(1)

总结

排序题的扩展考法
需要熟悉经典的排序方法
排序算法的时间和空间不可兼得，