Description

Given an unsorted arraynums, reorder it such that

nums[0] < nums[1] > nums[2] < nums[3]....

Notice

You may assume all input has valid answer.

Example

Givennums = [1, 5, 1, 1, 6, 4], one possible answer is[1, 4, 1, 5, 1, 6].

Givennums = [1, 3, 2, 2, 3, 1], one possible answer is[2, 3, 1, 3, 1, 2].

Solution

1. 用quick partition找到这串数组中的medium
   只要找到medium，不需要完整的sort整个数组，因此partition到position = length/2 - 1，返回对应的数即可

2. 创建一个新的数组，把他的每个元素都初始化成medium

3. 放两个指针在数组的头尾， left，right，这两个指针的特点是，一个指向波峰一个指向波谷，如此，遍历原数组时，将小于medium的数插到波谷对应的index，将大于medium的数插到波峰对应的index
   当数组长度为偶数时，left = 1为波峰，right = length - 2为波谷
   当数组长度为奇数时，left = 0为波谷，right = length - 2为波峰

4. 探讨这个方法是如何避免将相等的数放置到一起的
   原本想出来一个方法-- 先quick sort整个数组从小到大排列，放两个指针指向这个数组的头和尾，建一个新的数组，先放入头指针指向的最小数，再放入尾指针指向的最大数，再继续放入头指针指向的最小数，以此类推，就可以得到小大小...排列的数组
   这个方法的问题是最终头指针和尾指针都指到中间时，如果中间有好几个相等的数挨在一起导致头指针和尾指针指向的数相等时，放入新数组也将会把相等的数放到相邻的地方
   上面的方法是如何避免这个问题的呢：因为初始化讲所有的点都赋给了medium，在遍历的过程中将原数组和medium值对比，比medium大或者小的才放入新的数组并且移动left，right指针，和medium相等的点不做处理，因此没有被left和right指针指到过的点最后仍然是medium，而left和right指针因为是奇偶错开的，所以遍历到最后，两个指针不会像是上面这个错误的方法一样相遇到中间，而是远远的排列到一头一尾，因此medium值只会在头部的奇/偶点和尾部的偶/奇点。
   假设left指针是奇数位的，那么left指针从头指到靠近尾部某一奇数点的过程中，把从头到尾所有指到过的点都放入了比medium小的数，剩下尾部的一些没有指到过的奇数点仍然是medium，相应的头部的没有被right指到过的偶数点是medium，这些medium点是绝不会相邻的。

public class Solution {
    /**
     * @param nums a list of integer
     * @return void
     */
    public void wiggleSort(int[] nums) {
        // Write your code here
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = nums[i];
        }
        int medium = partition(nums, 0, nums.length - 1, nums.length/2);
        int ret[] = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ret[i] = medium;
        }

        if (nums.length % 2 == 0) {
            int left = 1; // large
            int right = nums.length - 2; // small
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < medium) {
                    ret[right] = nums[i];
                    right -= 2;
                } else if (nums[i] > medium) {
                    ret[left] = nums[i];
                    left += 2;
                }
            }
        } else {
            int left = 0; // small
            int right = nums.length - 2; // large
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < medium) {
                    ret[left] = nums[i];
                    left += 2;
                } else if (nums[i] > medium) {
                    ret[right] = nums[i];
                    right -= 2;
                }
            }
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = ret[i];
        }
    }

    private int partition(int[] nums, int l, int r, int pos) {
        int left = l;
        int right = r;
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;

        if (left == pos) {
            return pivot;
        } else if (left < pos) {
            return partition(nums, left+1, r, pos);
        } else {
            return partition(nums, l, left - 1, pos);
        }
    }
}