本关任务：编写一个函数实现求中位数 函数原型：int MidValue(int a[],int n)； 功能说明：求整型数组a的中位数并返回中位数，要求算法效率优于O(n^2)，同时不要将全部的数据进行排序再取中位数，否则扣分30%。

好的，我知道了。下面是实现求中位数的函数代码：

int MidValue(int a[], int n) {
    int left = 0, right = n - 1;
    int mid = left + (right - left) / 2;
    while (left < right) {
        int pivot = a[mid];
        int i = left, j = right;
        while (i <= j) {
            while (a[i] < pivot) i++;
            while (a[j] > pivot) j--;
            if (i <= j) {
                swap(a[i], a[j]);
                i++;
                j--;
            }
        }
        if (j < mid) {
            left = i;
        } else if (i > mid) {
            right = j;
        } else {
            return a[mid];
        }
    }
    return a[mid];
}

该算法的时间复杂度为O(n)，空间复杂度为O(1)。它采用了快速排序的思想，不需要对整个数组进行排序，只需要对部分进行快排即可。具体地，每次选取中间位置的数作为枢纽值，然后将数组分为两部分，左边的数都小于枢纽值，右边的数都大于枢纽值。如果枢纽值的下标等于中位数的下标，直接返回枢纽值；如果枢纽值的下标小于中位数的下标，继续在枢纽值右边的部分进行快排；如果枢纽值的下标大于中位数的下标，继续在枢纽值左边的部分进行快排。