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

可以使用快速选择（QuickSelect）算法来求解中位数，时间复杂度为O(n)。

具体实现如下：

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

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

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

快速选择算法的思路是：先选择一个pivot元素，然后将数组中小于pivot的元素放在左边，大于pivot的元素放在右边，这样pivot元素就排在了第pivotIdx个位置上。如果k恰好等于pivotIdx，则找到了中位数；如果k小于pivotIdx，则在左半部分继续查找；如果k大于pivotIdx，则在右半部分继续查找。由于每次可以将数组的大小缩小一半，所以时间复杂度为O(n)。

注意，快速选择算法虽然时间复杂度优于O(n^2)，但是最坏情况下的时间复杂度仍然是O(n^2)，因此在实际应用中需要根据具体情况进行评估。