一、项目背景详细介绍

在数据处理与算法设计中，**摆动排序（Wiggle Sort）**是一种经典的数组重排问题：将数组元素重新排列，使其呈现“峰-谷-峰-谷”交替上升和下降的形态。例如，对于输出要求 nums[0] <= nums[1] >= nums[2] <= nums[3]…。这一排序在信号处理、视觉排版、游戏开发等场景中都有独特应用：

1. 信号波形模拟

   • 擬合或模拟交替上升下降的信号波形。

2. 用户界面排列

   • 在页面布局中，将元素以交替大小或颜色突出显示。

3. 游戏关卡设计

   • 生成交替难度的关卡系数列表。

4. 面试考题

   • Wiggle Sort 属于滑动窗口与贪心策略结合的中级编程题，常考察对一趟线性遍历和条件交换的理解。

深入掌握摆动排序算法，有助于熟悉常见的原地变换、局部最优与全局调和，以及在 O(n) 时间／O(1) 空间内完成复杂排列的思路。

---

二、项目需求详细介绍

1. 功能需求

   • 提供工具类 WiggleSorter，包含两种静态方法：

public static void wiggleSortGreedy(int[] nums);
public static void wiggleSortSortSwap(int[] nums);

1. • wiggleSortGreedy：一次遍历，按需局部交换，O(n) 时间、O(1) 空间；

   • wiggleSortSortSwap：先排序再邻位交换，O(n log n) 时间、O(1) 额外空间。

2. 异常与边界

   • 若 nums 为 null，抛出 NullPointerException；

   • 长度小于 2 时无需修改，直接返回。

3. 性能需求

   • wiggleSortGreedy：线性时间，一趟遍历；

   • wiggleSortSortSwap：先排序（TimSort），再一趟交换；

4. 稳定性需求

   • 虽位置会变，但要保证不使用额外数组。

5. 可扩展性需求

   • 后续可扩展至 List<Integer> 泛型版本；

   • 支持两种模式：<=, >=, <=… 与 >=, <=, >=…。

---

三、相关技术详细介绍

1. 贪心原地遍历

   • 使用布尔标志 less = true，一趟遍历下标 i：

     • 若 less 且 nums[i] > nums[i+1]，交换；

     • 若 !less 且 nums[i] < nums[i+1]，交换；

     • 取反 less = !less；

2. 排序再交换

   • 先调用 Arrays.sort(nums)；

   • 对下标 i = 1; i + 1 < n; i += 2，交换 nums[i] 与 nums[i+1]；

3. 原地交换

   • 简单三步异或或借助临时变量交换值。

4. 数组与边界判断

   • 遍历时需保证 i+1 < n。

---

四、实现思路详细介绍

4.1 贪心一次遍历

1. 初始化

   • 布尔 less = true 表示当前期望 nums[i] <= nums[i+1]。

2. 遍历交换

for (int i = 0; i + 1 < n; i++) {
    if (less) {
        if (nums[i] > nums[i+1]) swap(nums, i, i+1);
    } else {
        if (nums[i] < nums[i+1]) swap(nums, i, i+1);
    }
    less = !less;
}

1. 结果性质

   • 因为每一步只保证局部顺序，最终达到全局摆动。

4.2 排序再交换

1. 排序

   • Arrays.sort(nums)；

2. 邻位交换

for (int i = 1; i + 1 < n; i += 2) {
    swap(nums, i, i+1);
}

1. 复杂度

   • 排序占主导 O(n log n)。

---

五、完整实现代码

// ===== 文件：WiggleSorter.java =====
package com.example.wiggle;

import java.util.Arrays;
import java.util.Objects;

/**
 * WiggleSorter 工具类：实现摆动排序（Wiggle Sort）
 */
public class WiggleSorter {

    /**
     * 方法一：贪心一次遍历，交替比较并交换
     * 时间 O(n)，空间 O(1)
     */
    public static void wiggleSortGreedy(int[] nums) {
        Objects.requireNonNull(nums, "输入数组不能为空");
        int n = nums.length;
        boolean less = true;
        for (int i = 0; i + 1 < n; i++) {
            if (less) {
                if (nums[i] > nums[i+1]) {
                    swap(nums, i, i+1);
                }
            } else {
                if (nums[i] < nums[i+1]) {
                    swap(nums, i, i+1);
                }
            }
            less = !less;
        }
    }

    /**
     * 方法二：先排序再邻位交换
     * 时间 O(n log n)，空间 O(1)
     */
    public static void wiggleSortSortSwap(int[] nums) {
        Objects.requireNonNull(nums, "输入数组不能为空");
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 1; i + 1 < n; i += 2) {
            swap(nums, i, i+1);
        }
    }

    // 原地交换辅助方法
    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

// ===== 文件：Main.java =====
package com.example.wiggle;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {3, 5, 2, 1, 6, 4};
        WiggleSorter.wiggleSortGreedy(arr1);
        System.out.println("Greedy Sort:     " + Arrays.toString(arr1));

        int[] arr2 = {3, 5, 2, 1, 6, 4};
        WiggleSorter.wiggleSortSortSwap(arr2);
        System.out.println("Sort-Then-Swap:  " + Arrays.toString(arr2));
    }
}

六、代码详细解读

• wiggleSortGreedy

  • 使用布尔标志 less 控制当前比较方向，保证交替<=/>=关系；

  • 一次遍历即可完成原地重排。

• wiggleSortSortSwap

  • 先全局排序，再在每个奇数下标与后继位置交换，构造摆动效果。

• swap

  • 简单的三步变量交换，无额外开销。

---

七、项目详细总结

1. 算法对比

   • 贪心法：O(n) 时间，最优；

   • 排序法：O(n log n) 时间，更易理解但性能次之。

2. 原地与稳定性

   • 两种方法都在原数组就地变换，无额外数组；

   • 写位置交换但不保证稳定排序（值相等时位置可变）。

3. 适用场景

   • 当需要线性时间并对大数据处理时，推荐贪心法；

   • 教学或非性能关键场景，可用排序法快速实现。

---

八、项目常见问题及解答

1. 为什么 wiggleSortGreedy 总能正确？
   因为局部交替交换逐步构造全局摆动，无需回溯或二次遍历。

2. 是否支持相等元素？
   相等时不交换，可保持相对位置或任意性。

3. 如何改为 nums[0] >= nums[1] <= nums[2] … 模式？
   初始 less = false 即可翻转第一步方向。

4. 贪心法对最坏输入有无退化？
   无论输入如何，只需一趟遍历，始终 O(n)。

5. 能否对 List<Integer> 使用？
   可将方法泛化，替换 int[] 为 List<T> 并使用 Collections.swap。

---

九、扩展方向与性能优化

1. 并行化处理

   • 对非常大的数组，可分段并行摆动再合并边界，挑战在于段边界方向衔接。

2. 流式 API

   • 提供 IntUnaryOperator 或 Function<int[],int[]>，便于在流中 map。

3. 异步输出

   • 对实时数据流，按接收到的元素动态维护摆动序列。

4. 可视化演示

   • 在 GUI 中实时展示数组值随时间的摆动变化。

5. 算法变体

   • 探索 wiggleMax：使局部峰谷幅度最大化的重排问题。