# 1ms Java Solution with Clear Example

• Use {1,3,6,9,8,2} as input data.
Step 1: make each [even, odd] pair to be [small, large] --> {1,3,6,9,2,8}
Step 2: make each [odd, even] pair to be [large, small] --> {1,6,3,9,2,8} Done!

``````public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i += 2)
if (nums[i] < nums[i - 1]) swap(nums, i, i - 1);
for (int i = 2; i < nums.length; i += 2)
if (nums[i] > nums[i - 1]) swap(nums, i, i - 1);
}

public void swap(int[] a, int p, int q) {
int t = a[p];
a[p] = a[q];
a[q] = t;
}
``````

A fancy swap method like:

``````public void swap(int[] a, int p, int q) {
a[p] = a[p] + a[q];
a[q] = a[p] - a[q];
a[p] = a[p] - a[q];
}``````

• very impressive !!　can you explain why?

• This post is deleted!

• @MissYu
Making [even, odd] pairs to be [small, large] will ensure the number before the odd index will be smaller than itself.
Making [odd, even] pairs to be [large, small] will ensure the number after the odd index will be larger than itself.
How to prove?
Assume we have the following sequence after finishing the first round of exchange:
[a1, a, b1, b, c1, c] here a1<a, b1<b, c1<c and this is guaranteed by the first switch.
So, here we need to do the second switch for pairs [odd, even],
Starting from [a, b1],
if a>b1, we do not need to switch the element, continue to the next [odd, even] pair.
if a<b1, we did the switch and make it become:
[a1, b1, a, b, c1, c]
here because a1<a, a<b1, so a1<b1. so we have a1<b1>a.
And so forth.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.