奇偶调序（新的步骤实现）

奇偶调序（新的方法实现）
调整数组顺序使奇数位于偶数前面。
题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

分析：

你当然可以从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，只是这种方法总的时间复杂度是O(n^２)，不符合要求，pass。
很简单，维护两个指针，一个指针指向数组的第一个数字，向后移动；一个个指针指向最后一个数字，向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

思路有了，接下来，写代码实现：

// Reorder.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

bool isEvent(int num)
{
	return ((num&1)==0);
}
void Reorder(int* pData,unsigned int len)
{
	int* pBegin=pData;
	int* pEnd=pData+len-1;
	int* a=pData;
	int temp=0;//用于交换
	while (pBegin<pEnd)
	{
		if (isEvent(*pBegin) && !isEvent(*pEnd))//如果前面是偶数
		{	
			//交换
			temp=*pBegin;
			*pBegin=*pEnd;
			*pEnd=temp;
			pBegin++;
			pEnd--;
		}
		else
		{
			pBegin++;//只去移动奇数的指针
	
		}
	}

}

void ReorderOddEven(int *pData,unsigned int len)
{
	if (pData==NULL|| len==0)
	{
		return ;
	}
	Reorder(pData,len);
}


int _tmain(int argc, _TCHAR* argv[])
{
	int a[]={2,1,3,4,6,5,7};
	int len=sizeof(a)/sizeof(int);
	ReorderOddEven(a,len);
	for (int i=0;i<len;i++)
	{
		cout<<a[i];
	}
	cout<<endl;
	


	system("pause");
	return 0;
}

奇偶调序（新的步骤实现）

相关推荐