排序算法之：排序数组中的“摆动排序 II”（Wiggle Sort II）的进阶优化与分治策略

1. 题目描述

给定一个无序整数数组 nums，要求将其重新排列成 “摆动排序” 顺序：
对于任意位置 i（索引从 0 开始），满足：

nums[0] < nums[1] > nums[2] < nums[3] > ...

换句话说：奇数位置的元素大于其相邻的两个偶数位置的元素（即局部呈现“小-大-小-大”的波浪形态）。
本题是 “摆动排序 I” 的进阶版，在 I 中条件为 nums[0] <= nums[1] >= nums[2] <= ...（允许相等），而 II 要求严格“<”和“>”，且可能存在重复元素。

示例：
输入：nums = [1,5,1,1,6,4]
输出可能的摆动排序结果：[1,6,1,5,1,4]（或 [1,4,1,5,1,6] 等）

约束：

• 数组长度 n 可能较大（例如 10^5）。
• 要求 原地排序（空间复杂度 O(1) 额外空间，除了函数调用栈）。

2. 解题思路的循序渐进讲解

步骤 1：理解问题的本质

我们需要将数组重新排列，使得：

• 所有偶数索引（0, 2, 4, …）的元素小于相邻的奇数索引（1, 3, 5, …）的元素。
• 如果简单排序后直接交叉放置（例如排序后前半部分放偶数位、后半部分放奇数位），可能因为 中位数附近重复元素过多 而导致相邻相等，违反“>”和“<”的严格要求。

步骤 2：一个关键观察

假设数组已排序为 sorted，长度为 n。
一种直觉方法是：
将排序后的数组分成两半：

• 前半部分 L = sorted[0 .. mid-1]（较小的一半）
• 后半部分 R = sorted[mid .. n-1]（较大的一半）

如果直接按顺序将 L 放在偶数位、R 放在奇数位，可能会在中间附近出现重复值相邻的情况（当数组中位数有重复时）。
解决方案：将 L 和 R 分别 逆序 后再交叉放置。

为什么逆序可以避免相邻相等？
举例：假设排序后 sorted = [1,1,1,2,2,3]，mid=3，则 L=[1,1,1]，R=[2,2,3]。
直接交叉：[1,2,1,2,1,3] → 在第 2 位和第 3 位出现 1,2 后，第 3 位和第 4 位是 2,1，检查发现 nums[3]（值 2）和 nums[4]（值 1）不满足 nums[3] > nums[4] 吗？等等，我们需要仔细映射索引。

实际上，更安全的方法是：

• 将较小的一半放在偶数索引（0,2,4,...）
• 将较大的一半放在奇数索引（1,3,5,...）
• 但为了严格避免中间重复值相邻，我们需要 从两半的末尾开始取元素（即逆序放置），这样可以确保中位数重复值被尽可能分开。

步骤 3：标准算法流程（三步法）

给定数组 nums：

1. 找到数组中位数（即第 k = n/2 大的数，可以用 快速选择 算法在平均 O(n) 时间、O(1) 额外空间完成）。
2. 使用 三分法（类似荷兰国旗问题）将数组按中位数划分为三部分：
   • 小于中位数的放左边
   • 等于中位数的放中间
   • 大于中位数的放右边
     这一步称为 “三路划分”（3-way partition），目的是将所有等于中位数的元素聚集在中间。
3. 重新映射索引，将较小的一半（包括小于和部分等于中位数的元素）放到偶数索引，较大的一半（包括大于和部分等于中位数的元素）放到奇数索引，同时为了分开重复值，采用 从后往前 放置的方式。

步骤 4：索引映射的巧妙设计

如果直接在原数组上交换，我们需要一个映射函数，将“虚拟”的排序后数组的逆序交叉放置映射到实际索引。
一种已知的 “虚拟索引” 方法（O(1) 空间）：

• 定义映射 index = (2*i + 1) % (n | 1)，其中 n | 1 表示如果 n 是偶数则加 1（取大于 n 的最近奇数）。这个映射可以将原数组索引重新排列成“奇数位全部在数组前半部分，偶数位在后半部分”的虚拟顺序，方便我们进行三路划分后的放置。

具体操作：

1. 用快速选择找到中位数 median。
2. 使用三个指针：low, mid, high，在 虚拟索引空间 上进行三路划分：
   • 当前元素小于 median → 交换到虚拟索引的前部（low 区）
   • 当前元素等于 median → 留在中部（mid 区）
   • 当前元素大于 median → 交换到虚拟索引的后部（high 区）
3. 划分完成后，数组在虚拟索引上已经满足：前部是较小元素，后部是较大元素，且重复的中间值被分散开。

这样，当我们按实际索引访问时，自然就是“摆动排序”的结果。

步骤 5：举例说明

以 nums = [1,5,1,1,6,4] 为例：

1. 排序后 [1,1,1,4,5,6]，中位数是 (1+4)/2？不，中位数是排序后第 3 小的数（索引 2），值为 1，但实际上我们选择中位数作为划分值，这里选择 1（但重复多）。
   更好的办法是快速选择找到第 k = n/2 大的数（即第 3 小的数），这里是 1。

2. 三路划分（以中位数=1）：
   原数组：[1,5,1,1,6,4]
   虚拟索引映射（n=6，n|1=7）：
   实际索引 i → 虚拟索引 j = (2*i+1) % 7
   i=0 → j=1
   i=1 → j=3
   i=2 → j=5
   i=3 → j=0
   i=4 → j=2
   i=5 → j=4
   虚拟索引顺序：[nums[3], nums[0], nums[4], nums[1], nums[5], nums[2]] = [1,1,6,5,4,1]

   在虚拟索引空间进行三路划分（以中位数=1）：

   • 小于 1：无
   • 等于 1：[1,1,1]
   • 大于 1：[6,5,4]
     划分后虚拟数组：[1,1,1,6,5,4]（等于在前，大于在后，但我们需要较小一半在偶数虚拟索引，较大一半在奇数虚拟索引？这里要调整）

   实际上经典算法（LeetCode 324）的做法是：

   • 先三路划分把数组分成三部分（小于、等于、大于中位数）。
   • 然后将小于和等于中位数的部分放在偶数实际索引（通过虚拟索引映射实现），大于中位数的放奇数实际索引。
     通过逆序放置（从各部分的末尾取）来避免相等相邻。

步骤 6：最终算法（O(n) 时间，O(1) 空间）

1. 找到中位数 median（用快速选择算法，O(n)）。
2. 定义函数 virtual_index(i) = (2*i + 1) % (n | 1)。
3. 三路划分（在虚拟索引空间）：
   low = 0, high = n-1, mid = 0
   while mid <= high:
       if nums[virtual_index(mid)] < median:
           交换 nums[virtual_index(mid)] 和 nums[virtual_index(low)]
           low++, mid++
       else if nums[virtual_index(mid)] > median:
           交换 nums[virtual_index(mid)] 和 nums[virtual_index(high)]
           high--
       else:
           mid++
4. 结束。

为什么这样做能保证摆动顺序？

• 三路划分确保所有小于中位数的在“小半区”，大于的在“大半区”。
• 虚拟索引映射将实际偶数索引映射到数组前半部分（小半区），实际奇数索引映射到数组后半部分（大半区）。
• 逆序放置（通过从 high 向前扫描和 low 向后扫描自然实现）确保中间重复值被分开。

3. 复杂度分析

• 时间复杂度：
  快速选择中位数 O(n)（平均情况，最坏 O(n²)，但可以用 BFPRT 算法保证 O(n)）。
  三路划分 O(n)。
  总体 O(n)。
• 空间复杂度：O(1)（原地操作）。

4. 总结

“摆动排序 II” 的核心挑战在于 严格的大于/小于关系 和 重复元素的处理。通过结合：

1. 中位数选择（快速选择）
2. 三路划分（荷兰国旗变形）
3. 虚拟索引映射（实现交叉放置）

我们可以在 O(n) 时间、O(1) 空间内完成原地重排。这个算法体现了分治（快速选择）和数组索引映射的巧妙运用，是排序问题与排列问题结合的经典例题。