This is not a O(n) solution like the other posts. I just want to give another way to solve this problem.

First sort the array, then use perfect shuffle algorithm to rerange it.

Take `[3, 1, 4, 8, 2, 9]`

as axample, first sort it to `[1, 2, 3, 4, 8, 9]`

, then shuffle it to `[1, 4, 2, 8, 3, 9]`

.

```
class Solution(object):
def reverse(self, start, end):
low, high = start, end
while low < high:
self.nums[low], self.nums[high] = self.nums[high], self.nums[low]
low += 1
high -= 1
def getK(self, n):
k, square = 1, 3
while square - 1 <= 2 * n:
k += 1
square *= 3
return k - 1
def shuffle(self, start, end):
n = (end - start + 1) / 2
k = self.getK(n)
m = (3 ** k - 1) / 2
if m != n:
self.reverse(start + m, start + n - 1)
self.reverse(start + n, start + n + m - 1)
self.reverse(start + m, start + n + m - 1)
for k in xrange(1, k + 1):
i = cursor = 3 ** (k - 1)
pre, visited = self.nums[i + start - 1], False
while not (i == cursor and visited):
i = (2 * i) % (2 * m + 1)
self.nums[i + start - 1], pre = pre, self.nums[i + start - 1]
if not visited:
visited = True
if n != m:
self.shuffle(start + 2 * m, end)
def wiggleSort(self, nums):
length = len(nums)
if length < 2:
return
nums.sort()
start, end = 1, length - 1
if not length & 1:
end -= 1
self.nums = nums
self.shuffle(start, end)
```