#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int len = nums.size();
if(len < 2) return ;
int median = quicksort(0, len - 1, nums,(len+1)/2);
int i = 0, j = 0, k = len - 1;
vector <int> nums1=nums;
while(i < (k/2+1)) {
nums[j++]=nums1[i];
if(j<=k){
nums[j++]=nums1[k/2+1+i];
}
i++;
}
}
int transformInd(int i, int len) {
if(i < (len >> 1)) return i*2+1;
else return (i - (len>>1))*2;
}
int quicksort(int left,int right,vector<int>& nums,int n){
if(left >= right) return nums[right];
int i=left,j=right+1;
int key=nums[left];
while(i < j) {
while(++i < right && nums[i] < key);
while(--j > left && nums[j] > key);
if(i >= j) break;
swap(nums[i], nums[j]);
}
swap(nums[left], nums[j]);
if(n == j ) return nums[j];
else if(n<j ) return quicksort(left,j-1,nums,n);
else return quicksort(j+1,right,nums,n );
}
};
int main(){
vector <int> nums;
Solution wiggle;
/* for(int i = 0; i < 5; i++ )
{
nums.push_back( i );//把元素一个一个存入到vector中
}*/
nums.push_back( 4 );
nums.push_back( 5 );
nums.push_back( 5 );
nums.push_back( 6 );
/* nums.push_back( 6 );
nums.push_back( 4 );*/
// nums.push_back( 1 );
wiggle.wiggleSort(nums);
for(int i=0;i<4;i++){
cout<<nums[i]<<endl;
}
system("pause");
return 0;
}
