链接：

题解：

1.先用partition函数，求得n/2的位置的排序

2.然后选取首尾指针（奇数选择1和length-1，偶数选择为1和length-2），进行swap交换

3.每次首指针每次+2，尾指针每次-2

九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

 

 

 

 

 

这段代码没有通过

class Solution {
public:/*** @param nums: A list of integers* @return: nothing*/void wiggleSort(vector<int> &nums) {// write your code hereif (nums.size() <= 1) {return;}int len = nums.size();kthLargestElement(len/2, nums);if (len % 2 == 0) {int left = 1;int right = nums.size()-2;while (left < right) {swap(nums[left], nums[right]);left += 2;right -= 2;}} else {int left = 1;int right = nums.size() - 1;while (left < right) {swap(nums[left], nums[right]);left += 2;right -= 2;}}}private:int kthLargestElement(int k, vector<int> &nums) {cout << "k=" << k << endl;// write your code hereif (nums.size() <= 0) {return 0;}int left = 0;int right = nums.size()-1;int mid = partition(nums, left, right);//cout << "mid=" << mid << endl;while (mid != k-1) {//cout << "mid=====" << mid << endl;if (mid > k) {right = mid;} else {left = mid;}mid = partition(nums, left, right);}return nums[mid];}int partition(std::vector<int>& nums, int left, int right) {int index = random() % (right-left+1);swap(nums[right], nums[left+index]);int nSmall = left - 1;for (; left < right; ++left) {if (nums[left] <= nums[right]) {++nSmall;swap(nums[left], nums[nSmall]);}}++nSmall;swap(nums[right], nums[nSmall]);cout << nSmall << " val=" << nums[nSmall] << endl;  return nSmall;}
};