按奇偶排序数组 II

记住这套「偶位放偶数、奇位放奇数，i 和 j 各跳 2」，下面每一帧都在套它。

先看规则:下标是偶数的格子要放偶数，下标是奇数的格子要放奇数。现在这个数组还没摆好。

放两个指针:偶位指针标 i 从 0 起，奇位指针标 r(就是代码里的 j)从 1 起。i 只落偶数下标、j 只落奇数下标，各跳 2 步。

红色这 4 个都放错了:偶位 0 和 2 上是奇数 3、5，奇位 1 和 5 上是偶数 4、2。它们正好两两配对，一次交换能同时修好两处。

i 跳到偶位 0，看看上面是什么:这里是 3。

3 是奇数，却站在偶位 0，放错了(变红)。要去奇位那边找一个放错的偶数来跟它换。

j 到奇位 1，这里是 4，偶数却站在奇位，正是放错的，就用它跟偶位 0 交换。

交换:偶位 0 拿到偶数 4，奇位 1 拿到奇数 3，两边同时归位(变绿)。

i 跳到偶位 2，看看上面是什么:这里是 5。

5 是奇数，却站在偶位 2，放错了(变红)。要去奇位那边找一个放错的偶数来跟它换。

j 在奇位 1，这里是 3，奇数待在奇位是对的，不能动，j 加 2 接着往后找。

j 在奇位 3，这里是 7，奇数待在奇位是对的，不能动，j 加 2 接着往后找。

j 到奇位 5，这里是 2，偶数却站在奇位，正是放错的，就用它跟偶位 2 交换。

交换:偶位 2 拿到偶数 2，奇位 5 拿到奇数 5，两边同时归位(变绿)。

i 跳到偶位 4，看看上面是什么:这里是 6。

6 是偶数，正好站在偶位 4，本来就对(变绿)，跳过，i 接着往后走。

i 跳到偶位 6，看看上面是什么:这里是 8。

8 是偶数，正好站在偶位 6，本来就对(变绿)，跳过，i 接着往后走。

i 把偶位 0、2、4、6 都看过了，循环结束。下面逐位验收一下结果。

先看偶位:0、2、4、6 上分别是 4、2、6、8，全是偶数，符合要求。

再看奇位:1、3、5、7 上分别是 3、7、5、1，全是奇数，也符合要求。

整个数组摆好了:偶位放偶数、奇位放奇数。答案就是 [4,3,2,7,6,5,8,1]。

边界想清:本就合规直接过、一对错位换一次、最坏也只一趟。

两个高频追问:不回头保证不破坏、原地交换满足 O(1) 空间。