链接：摆动排序 II

方法一：排序后+翻转子数组

将数组排序后，分割成两个数组a、b，a的长度等于b或者大1。然后将a、b两个数组的元素轮流插入到原数组中。但是，在中位数元素出现超过次数大于半数时，会出现两个中位数排在一起，不满足本题严格大于小于的要求。解决方法是将a、b翻转后在进行轮流插入。

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        arr = sorted(nums)
        m = (len(nums)+1) // 2
        arr1 = arr[:m][::-1]
        arr2 = arr[m:][::-1]

        for i in range(len(arr1)):
            nums[2*i] = arr1[i]
        for i in range(len(arr2)):
            nums[2*i+1] = arr2[i]

方法二：快速选择 + 3-way-partition

使用快速排序中的partition函数，来找到中位数的值，然后使用三路partition方法对nums数组进行划分，形成四个区间，都小于，都等于，为未处理区间，都大于。遍历时移动，当时结束循环。

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # midval = self.partition(nums, 0, len(nums)-1, len(nums)//2)
        t = nums.copy()
        midval = sorted(t)[len(t)//2]
        # print(midval)

        # [0, i-1], [i, j-1] [j, k-1] , [k,n-1]
        i = 0
        j = 0
        k = len(nums)
        while j < k:
            if nums[j] > midval:
                k -= 1
                nums[j], nums[k] = nums[k], nums[j]
            elif nums[j] < midval:
                nums[j], nums[i] = nums[i], nums[j]
                i += 1
                j += 1
            else:
                j += 1

        mid = (len(nums)+1)//2
        arr1 = nums[:mid][::-1]
        arr2 = nums[mid:][::-1]
        for i in range(len(arr1)):
            nums[2*i] = arr1[i]
        for i in range(len(arr2)):
            nums[2*i+1] = arr2[i]

    def partition(self, nums, l, r, t):
        m = random.randint(l,r)
        nums[r], nums[m] = nums[m], nums[r]

        #[l, i-1], [i, k], [k+1, r]
        i = l
        pivot = nums[r]
        for k in range(l, r):
            if nums[k] <= pivot:
                nums[i], nums[k] = nums[k], nums[i]
                i += 1
        nums[i], nums[r] = nums[r], nums[i]
        # print("nums:{}, l:{}, r:{}, m:{}".format( nums, l, r, i))
        if i == t:
            return nums[i]
        elif i < t:
            return self.partition(nums, i+1, r, t)
        else:
            return self.partition(nums, l, i-1, t)