280. Wiggle Sort

The final sorted array must follow:
1. If i is odd, nums[i] >= nums[i-1]
2. If i is even, nums[i] <= nums[i-1]
The invariance is that nums[i-1] has been wiggle sorted. If i is odd, nums[i-1] <= nums[i-2]. So if nums[i] < nums[i-1], it must satisfy nums[i] < nums[i-2], so swapping nums[i] and nums[i-1] doesn’t break the invariance, and especially, after swapping, the invariance is kept till nums[i]. Same to the case of even i.

1:  class Solution {  
2:  public:  
3:    void wiggleSort(vector<int>& nums) {  
4:      for (int i = 1; i < nums.size(); i++) {  
5:        if (((i & 1) && nums[i] < nums[i-1]) || (!(i & 1) && nums[i] > nums[i-1])) {  
6:          swap(nums[i], nums[i-1]);  
7:        }  
8:      }  
9:    }  
10:  };