1. wiggle sort
2. wiggle sort II

1. Wiggle Sort

1. O(nlogn): Sort first + starting from the second elements, swap two continuous elements
2. O(n) : swap elements based on even or odd index

• 先sort，然后从第二个元素开始，swap(2nd, 3rd), swap(4th, 5th)....这样子就可以得到一个wiggle sorted array

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i+=2) {
            if (i + 1 < nums.length) swap(nums, i, i + 1);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

• 可以总结出一个规律

  • 当i为奇数时，nums[i] >= nums[i - 1] --> 要大于或者等于前一位

  • 当i为偶数时，nums[i] <= nums[i - 1] --> 要小于或者等于前一位

  如果不符合，则与前一位数字交换

//todo wiggle sort ii