324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

参考了答案，比较不解的是最后的循环部分， 对于奇数和偶数部分，处理的不一样：
偶数位置且该位置的值大于mid，那么必须交换，然后去往下一个待交换的i；
奇数位置且该位置的是小于mid，那么用大的数值放上；
注意j指向的位置，偶数长度的数组指向中间两个元素的最后一个，奇数长度的数组指向中间那个的位置；
为什么还有p>i , p<j 的情况呢？我认为是只要小于j都要交换，相当于从右边插入，得到满足要求的wiggle序列，直到p已经大于j；
p>i也是一样，有些子序列情况，比如p的值等于mid,这时候跳过了第一个i=1， i=1而p已经大于i了，这时候相当于i这个位置的值还未找到合适的替代；总之比较麻烦，需要多看下这个。

class Solution {
public:
    //找中间最大的数，然后二分这个数组，
    // 逐个插入mid左边小的元素到右边大的元素中间
    void wiggleSort(vector<int>& nums) {
        int length = nums.size();
        auto midptr = nums.begin() + length / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;
        // j在偶数的时候指向中间两个数的后者，奇数的时候就是中间那个数的index；
        //i永远指向大于两边的位置上。
        int p=0, i=1, j= length % 2 == 0 ? length-2: length-1;
        
        while(p<length)
        {
            if (nums[p]>mid && (p>i || p%2==0))
            {
                swap(nums[p], nums[i]);
                i += 2;
            }
            else if (nums[p]<mid && (p<j || p%2==1))
            {
                swap(nums[p], nums[j]);
                j -= 2;
            }
            else
                p++;
        }
        
    }
};