首页 > 代码库 > 调整数组顺序使得奇数位于偶数前面

调整数组顺序使得奇数位于偶数前面

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

代码:

/*
调整数组顺序使得奇数位于偶数前面
by Rowandjj
2014/8/1
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
//高效解法,但会调整后的数组元素相对顺序会发生改变
void func(int *pArr,int len)
{
	if(pArr == NULL || len <= 1)
	{
		return;
	}
	int low = 0,high = len-1;
	while(low < high)
	{
		while(low < high && (pArr[low] & 0x1) != 0)//low指针后移直到遇到偶数
		{
			low++;
		}
		while(low < high && (pArr[high] & 0x1) == 0)//high指针前移直到遇到奇数
		{
			high--;
		}
		if(low < high)//如果low指针在high指针前面,那就将两个指针所指元素互换
		{
			int temp = pArr[low];
			pArr[low] = pArr[high];
			pArr[high] = temp;
		}
	}
}
//使用辅助数组
void func2(int *pArr,int len)
{
	if(pArr == NULL || len <= 1)
	{
		return;
	}
	int *temp = (int*)malloc(sizeof(int)*len);
	if(!temp)
	{
		exit(-1);
	}
	int i,j = 0;
	for(i = 0 ; i< len; i++)//先将奇数复制到辅助数组前面
	{
		if((pArr[i] & 0x1) !=0)
		{
			temp[j++] = pArr[i];
		}
	}
	for(i = 0; i < len; i++)//再将偶数复制到辅助数组后面
	{
		if((pArr[i] & 0x1) == 0)
		{
			temp[j++] = pArr[i];
		}
	}
	for(i = 0; i < len; i++)//覆盖原数组
	{
		pArr[i] = temp[i];
	}
	free(temp);
}
int main()
{
	int n;
	cin>>n;
	if(n <= 0)
	{
		return 0;
	}
	int *pArr = (int*)malloc(sizeof(int)*n);
	if(!pArr)
	{
		return 0;
	}
	for(int i = 0; i < n; i++)
	{
		cin>>*(pArr+i);
	}
	func2(pArr,n);
	for(int j = 0; j < n; j++)
	{
		if(j == n-1)
		{
			cout<<*(pArr+j)<<"\n";
		}else
		{
			cout<<*(pArr+j)<<" ";
		}
	}
	free(pArr);
	return 0;
}