解題說明
Wiggle Sort
題目描述：
給定一個未排序的整數陣列 nums，原地重新排列使得 nums[0] <= nums[1] >= nums[2] <= nums[3] >= ...，即奇數索引的元素不小於相鄰元素，偶數索引的元素不大於相鄰元素。
解題思路： 觀察規律：
- 偶數索引
i：nums[i] <= nums[i+1] - 奇數索引
i：nums[i] >= nums[i+1]
只需一次遍歷：對於每個位置 i，檢查是否違反上述條件。若違反，將 nums[i] 和 nums[i-1] 交換即可。
為什麼交換是安全的？
- 若
i為奇數且nums[i] < nums[i-1]：交換後nums[i-1]變小，不會破壞i-1（偶數位）的<=條件。 - 若
i為偶數且nums[i] > nums[i-1]：交換後nums[i-1]變大，不會破壞i-1（奇數位）的>=條件。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單次遍歷陣列，每個元素最多檢查和交換一次。
空間複雜度：O(1) — 原地操作，只用常數額外空間。
虛擬碼
1. For each index i from 1 to n-1: a. If i is odd and nums[i] < nums[i-1]: swap nums[i] and nums[i-1] b. If i is even and nums[i] > nums[i-1]: swap nums[i] and nums[i-1]
其他解法
排序 + 交換 O(n log n)：先排序陣列，再從索引 2 開始每隔一個交換相鄰元素（swap(nums[i], nums[i-1]) for i = 2, 4, 6, ...）。排序保證小值在前，交換產生鋸齒形。正確但時間複雜度不如貪心法。
三路分區 + 交叉放置 O(n)：類似 Wiggle Sort II（LeetCode 324）的做法，先找中位數再三路分區。對本題而言過度設計，因為本題允許相等（<= 和 >=），不需要嚴格交替。
延伸思考
- 如果條件改為嚴格不等式
nums[0] < nums[1] > nums[2] < nums[3] > ...（LeetCode 324 Wiggle Sort II），為什麼簡單交換法不再適用？ - 貪心交換法的正確性證明：為什麼修復當前位置不會破壞已修復的前一個位置？
- 如果要求字典序最小的 wiggle 排列，該如何修改算法？