Lintcode-中位数

问题描述：

给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

思路一：

可以使用快速排序将数组排好序，然后返回中位数，这样做的时间复杂度是O(nlogn).

思路二：

为了降低复杂度，现在我们使用“折半的快速排序”。就是每一次只对一边的数组进行排序。

示例代码：

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    int Qsort(vector<int>&nums,int low,int high)//这里需要用引用
    {
        int i=low;
        int j=high;
        //int key=nums[0];
    //刚开始快速排序我一直是这么写的，然后一直AC不了。
//但是只测试快排又是可以运行出结果的，所以我一直以为是median函数里出错了。
//一直调试了很久很久，几个小时。所以这件事情也让我明白了基础扎实是很重要的。
        int key=nums[low];
        while (i<j)
        {
            while (i<j&&nums[j]>=key)
            {
                j--;
            }
            swap(nums[i],nums[j]);
            while (i<j&&nums[i]<=key)
            {
                i++;
            }
            swap(nums[i],nums[j]);
        }
        //nums[i]=key;
        return i;
    }

    int median(vector<int> &nums) {
        // write your code here
        int n=nums.size();
        int key=0,k=0;
        int left=0,right=n-1;
        if(n%2==0) key=n/2-1;
        else
        {
            key=n/2;
        }
        k=Qsort(nums,0,n-1);
        while (k!=key)
        {
            if(k<key)
            {
                left=k+1;
                k=Qsort(nums,left,right);
            }
            else
            {
                right=k-1;
                k=Qsort(nums,left,right);
            }
        } 
        return nums[key];
    }
};

注意点1：

int Qsort(vector<int>&nums,int low,int high)//这里需要用引用
    {
        int i=low;
        int j=high;
        //int key=nums[0];
               ....
         }

刚开始快速排序我一直是这么写的，然后一直AC不了。但是只测试快排又是可以运行出结果的，所以我一直以为是median函数里出错了。一直调试了很久很久，几个小时。所以这件事情也让我明白了基础扎实是很重要的。

注意点2：

int key=0,k=0;
        int left=0,right=n-1;
        if(n%2==0) key=n/2-1;
        else
        {
            key=n/2;
        }
        k=Qsort(nums,0,n-1);
        while (k!=key)
        {
            if(k<key)
            {
                left=k+1;
                k=Qsort(nums,left,right);
            }
            else
            {
                right=k-1;
                k=Qsort(nums,left,right);
            }
        } 

while循环里的left和right怎么控制，以及每次Qsort的上下限也要注意。