用c语言编写一个函数int MidValue(int a[],int n)；实现求中位数，求整型数组a的中位数并返回中位数，要求算法效率优于O(n^2)，同时不要将全部的数据进行排序再取中位数

可以使用中位数的中位数（Median of Medians）算法来求解中位数，时间复杂度为O(n)。

具体实现如下：

int findMedian(int a[], int n) {
    if (n == 1) return a[0];
    int i, j;
    for (i = 0, j = 0; i < n - 1; i += 2, j++) {
        if (a[i] > a[i + 1]) {
            int tmp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = tmp;
        }
    }
    if (n % 2 == 1) {
        a[j] = a[n - 1];
        j++;
    }
    return findMedian(a, j);
}

int partition(int a[], int left, int right, int pivot) {
    int i = left, j = right;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }
    return i;
}

int quickSelect(int a[], int left, int right, int k) {
    if (left == right) return a[left];
    int n = right - left + 1;
    int median = findMedian(a + left, n);
    int pivotIdx = partition(a, left, right, median);
    if (k == pivotIdx) {
        return a[k];
    } else if (k < pivotIdx) {
        return quickSelect(a, left, pivotIdx - 1, k);
    } else {
        return quickSelect(a, pivotIdx, right, k);
    }
}

int MidValue(int a[], int n) {
    int midIdx = n / 2;
    return quickSelect(a, 0, n - 1, midIdx);
}

中位数的中位数算法的思路是：先将原数组分成若干组，每组大小为5。对每组进行排序，然后找出每组的中位数，将这些中位数组成一个新的数组。再对这个新数组求中位数，得到一个pivot元素。将原数组根据pivot元素进行划分，小于pivot的放在左边，大于pivot的放在右边。如果pivot恰好是中位数，则找到了中位数；如果pivot小于中位数，则在右半部分继续查找；如果pivot大于中位数，则在左半部分继续查找。由于每次可以将数组的大小缩小到原来的1/5，所以时间复杂度为O(n)。

注意，中位数的中位数算法虽然时间复杂度为O(n)，但是常数因子比较大，常用的排序算法（如快速排序）在实际应用中往往更加高效。