class Solution {
public void wiggleSort(int[] nums) {
if(nums==null || nums.length==0)
return;
//1.找出中位数
int mid = findMid(nums);
//3.荷兰国旗
int n = nums.length, left = -1, right = n, i=0;
while(i<right){
//换扩跳
if(nums[newIndex(i,n)] > mid)
swap(nums, newIndex(i++,n), newIndex(++left,n));
//换扩
else if(nums[newIndex(i,n)] < mid)
swap(nums, newIndex(i,n), newIndex(--right,n));
//跳
else
i++;
}
}
//2.坐标映射
public int newIndex(int i, int n){
return (1+2*i)%(n|1);
}
public int findMid(int[] nums){
int n = nums.length;
int i=-1, mid=(n-1)>>1;
int left=0, right=n-1;
while(i!=mid){
if(i>mid){
i = partition(nums, left, i-1);
}
else if(i<mid){
i = partition(nums, i+1, right);
}
}
return nums[mid];
}
//和普通的partition的区别: 大的在前面, 小的在后面
public int partition(int[] nums, int i, int j){
int pivot = nums[j];
int big=i-1, small=j, p=i;
while(p<small){
if(nums[p] >= pivot){
swap(nums, p++, ++big);
}
else{
swap(nums, p, --small);
}
}
//把pivot放在正确的位置上
swap(nums, p, j);
return p;
}
public void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}