剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

方法1：不要求稳定性：用前后指针分别指向偶数、奇数，然后数字互换

         （时间复杂度：O(n)，空间复杂度：O(1)）

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int len=nums.size();
        int temp=0,i=0,j=len-1;
        while(i<j)
        {
            while((nums[i]%2!=0)&&(i<j))//必须加判断 i<j，不然会越界 
            {
                i++; 
            }	
            while((nums[j]%2==0)&&(i<j))//必须加判断 i<j，不然会越界 
            {
                j--;
            }
            if((nums[i]%2==0)&&(nums[j]%2!=0))
            {
                temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
                i++;
                j--;
            }
        } 
        return nums;
    }
};

方法2：要求稳定性：（时间复杂度为O()）

/*
1.i 从左到右开始遍历，找到第一个偶数；

2.j 从 i+1 开始向后找，直到找到第一个奇数；

3.将 [ i , ... . j - 1 ] 的元素整体后移一位，最后将找到的奇数放入 i 位置，然后 i++；

4.终止条件，j 向后遍历查找失败，即后面没有奇数了

*/

//还可以用冒泡或者直接插入的方法

vector<int> reOrderArray(vector<int>& array) 
{
	int len=array.size();
	int i=0,j=0;
	int temp=0;
	
	while(i<len)
	{
		while(i<len&&array[i]%2!=0)
		{
			i++;
		}
		j=i+1;       
		while(j<len&&array[j]%2==0) 
		{
			j++;		
		}
		if(j<len)
		{
			temp=array[j];//必须是往后移动，否则会位置发动变化 
			for(int q=j;q>i;q--)
			{
				array[q]=array[q-1];
			}
			array[i]=temp;
		}	
		else
            break;	必须有 
	}
	return array;
	
}

方法3： 要求稳定性：（时间复杂度O(n)） 

 //用空间换时间

//首先统计奇数的个数，然后新建一个与原数组等长的数组，设置两个指针，

//奇数指针从0开始，偶数指针从奇数个数的末尾开始遍历填数。 

vector<int> reOrderArray(vector<int>& array) 
{
	int len=array.size();
	int num=0;
	int *result=new int[len];//声明动态数组 
	int j=0,o=len; 
	vector<int> r;
	
	for(int i=0;i<len;i++)
	{
		if(array[i]%2!=0)
		{
			num++;
		}
	}
	o=num;
	for(int i=0;i<len;i++)
	{
		if(array[i]%2!=0)
		{	if(j<num)	
			{
				result[j]=array[i];
				j++;
			}	
			
		}
		else
		{		
			if(o<len)
			{
				result[o]=array[i];
				o++;
			}
				
		}
			
	}
	
	for(int i=0;i<len;i++)
	{
		r.push_back(result[i]);
	}
	return r;
	
}