奇偶排序（Parity Sort）

奇偶排序

题目描述

给定长度为 n 的数组 a，有两种操作：

• 交换两个奇数位置上的元素
• 交换两个偶数位置上的元素

判断能否通过任意次操作将数组按非递减顺序排序。

解题思路

核心观察

奇数只能和奇数交换，偶数只能和偶数交换。这意味着：

• 排序后，每个位置的奇偶性必须与原数组该位置的奇偶性相同
• 我们只需要检查排序后数组的奇偶性是否与原数组一致

算法步骤

1. 提取每个位置的奇偶性：arr[i] % 2
2. 对原数组排序：sorted_arr = sorted(arr)
3. 提取排序后数组的奇偶性
4. 比较两者的奇偶性序列是否相同

代码实现

n = int(input())

arr = [int(x) for x in input().split()]

sorted_arr = sorted(arr)
flag = True

for i in range(n):
    if sorted_arr[i] % 2 != arr[i] % 2:
        print("NO")
        exit()

print("YES")

代码解析

• sorted_arr[i] % 2：排序后第 i 个元素的奇偶性
• arr[i] % 2：原数组第 i 个元素的奇偶性
• 如果两者不一致，说明该位置无法通过操作达到目标状态，输出 “NO”
• 全部一致则输出 “YES”

时间复杂度

• 排序：O(n log n)
• 遍历比较：O(n)
• 总计：O(n log n)