C++，输入n个有序的数据并存入某一维数组中，求该数组的中位数（中位数是指排列在有序数组中间的那个数，如果数据个数为偶数，则中位数等于中间那两个元素的平均值）。

可以使用快速选择算法来求解。该算法的时间复杂度为O(n)。

具体思路如下：

1. 首先找到数组中的中位数所在的位置p，如果n为奇数，p = (n-1)/2，如果n为偶数，p = n/2-1。

2. 对于数组中的每个元素，将其与中位数进行比较，如果小于中位数，则将其放在左边的数组中，如果大于中位数，则将其放在右边的数组中。如果等于中位数，则直接返回中位数。

3. 根据左右数组的大小关系，递归地对左边或右边的数组进行步骤1和步骤2的操作，直到找到中位数。

代码实现如下：

#include <iostream>
#include <algorithm>

using namespace std;

int quickSelect(int arr[], int left, int right, int k){
    if (left == right) return arr[left];

    int i = left, j = right;
    int pivot = arr[(left + right) / 2];

    while (i <= j){
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;

        if (i <= j){
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    if (k <= j) return quickSelect(arr, left, j, k);
    if (k >= i) return quickSelect(arr, i, right, k);

    return arr[k];
}

int main(){
    int n;
    cout << "请输入数组大小n：" << endl;
    cin >> n;

    int arr[n];
    cout << "请输入" << n << "个有序数：" << endl;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }

    int mid = quickSelect(arr, 0, n - 1, n / 2);
    if (n % 2 == 0){
        mid = (mid + quickSelect(arr, 0, n - 1, n / 2 - 1)) / 2;
    }

    cout << "该数组的中位数为：" << mid << endl;

    return 0;
}