#include <iostream>
#include <algorithm>
using namespace std;

void swap(int i,int j,int arr[]){
	int temp;
	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
} 

int main(){
	int n;
	cin>>n;
	int arr[n];
	int i = 0;
	for(int i = 0;i < n;i++){
		cin>>arr[i];
	}
	
	int odd = -1;
	int even = n;
	while(odd+1<even){
		if(arr[odd+1]%2==0){	//如果是偶数，则与偶数区的下一个位置交换，且偶数区扩大，即even--
			swap(odd+1,even-1,arr);
			even--;	// 注意不要odd++,即奇数区保持不动，因为交换过来的数据可能还是个偶数，需要再下一轮再判断一次
		}else{	//如果是奇数，则奇数区扩大 
			odd++; 
		}
	}
	
	sort(arr,arr+odd+1);
	sort(arr+even,arr+n);
	
	for(int i = 0;i<n;i++){
		cout<<arr[i]<<" ";
	}
	
	return 0;
}

初始奇数区指针odd=-1,偶数区指针even = 数组长度；即初始认为奇数区和偶数区都没有数据

之后就是判断奇数区下一个元素是奇数还是偶数

如果是偶数，则与偶数区下一个元素交换，偶数区长度+1，即even--；此时奇数区保持不动，因为我们能确定的是交换过去偶数区的必定是个偶数，但交换过来的是奇数还是偶数还得下一轮while再判断一下，因为odd指针不动

如果是奇数，则奇数区长度+1；

这样就把奇数和偶数各自分到一边，再排序即可。

类似可以处理以x为轴，将元素分为<=x区域和>x区域的题目