学步园

60、百度笔试题
给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。

要求：空间复杂度 O(1)，时间复杂度为 O（n）。

/*
60、百度笔试题
给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。
要求：空间复杂度 O(1)，时间复杂度为 O（n）。

so easy 快速排序partition的思想 同54题 
*/
#include<iostream>
#include<stdio.h>
using namespace std;

void swap(int *a,int *b)
{
	int t;  
    t=*a;  
    *a=*b;  
    *b=t; 
}

void adjust(int *a,int n)
{
	int i,j;
	
	i=0;j=0;
	while(i<n)
	{
		if(a[i]%2==1)//奇数交换 
		{
			swap(&a[i],&a[j]); 
			j++;
		}
		i++;
	}	
}

int main()
{
	int a[]={1,2,3,4,5,6,7,8,9};
	int b[]={1,1,3,4,6,6,6,5,5,7,8,8,9,9};
	int len,i;
	len=sizeof(a)/sizeof(int);

	for(i=0;i<len;i++)
		printf("%d",a[i]);
	printf("\n");
	adjust(a,len);//变换 
	for(i=0;i<len;i++)
		printf("%d",a[i]);
	printf("\n");
	
	printf("*****************\n");
	
	len=sizeof(b)/sizeof(int);
	for(i=0;i<len;i++)
		printf("%d",b[i]);
	printf("\n");
	adjust(b,len);//变换 
	for(i=0;i<len;i++)
		printf("%d",b[i]);
	printf("\n");
	
	return 0;
}