解题思路

本题可以使用分类加排序算法。

先遍历数组 $nums$，将所有奇数放入一个数组 $odd$，将所有偶数放入一个数组 $even$。

然后分别对 $odd$ 和 $even$ 进行升序排序。

最后将排序后的 $odd$ 放在前面，排序后的 $even$ 放在后面，合并得到答案。

题目内容

给定一个存放整数的数组 $nums$，请你重新排列数组，使得数组左边全部为奇数，右边全部为偶数。

同时要求：

• 左边的奇数部分按照升序排列；
• 右边的偶数部分按照升序排列。

本题答案唯一，请输出重新排列后的数组。

输入描述

输入共两行。

• 第一行为一个整数 $n$，表示数组 $nums$ 的长度。
• 第二行为 $n$ 个整数 $nums_0, nums_1, ..., nums_{n-1}$，数字之间以空格分隔。

输出描述

输出一行 $n$ 个整数，表示重新排列后的数组。

输出结果需要满足：所有奇数在左，所有偶数在右，且奇数部分和偶数部分分别为升序。

样例1

输入

6
1 2 3 4 5 6

输出

1 3 5 2 4 6

说明

奇数部分为 $1,3,5$，按照升序排列；偶数部分为 $2,4,6$，按照升序排列。

样例2

输入

5
2 4 6 1 3

输出

1 3 2 4 6

说明

奇数部分为 $1,3$，偶数部分为 $2,4,6$，两部分均为升序。

样例3

输入

7
9 4 7 2 5 8 1

输出

1 5 7 9 2 4 8

说明

奇数部分为 $1,5,7,9$，偶数部分为 $2,4,8$，均满足升序要求。

提示

• $1 \le n \le 10^5$
• $-10^9 \le nums_i \le 10^9$