给一列无序数组，求出中位数并给出算法的时间复杂度

若数组有奇数个元素，中位数是a[(n-1)/2]；若数组有偶数个元素，中位数为a[n/2-1]和a[n/2]两个数的平均值。这里为方便起见，假设数组为奇数个元素。

思路一：把无序数组排好序，取出中间的元素。时间复杂度取决于排序算法，最快是快速排序，O(nlogn)，或者是非比较的基数排序，时间为O(n),空间为O(n)。这明显不是我们想要的。

思路二：采用快速排序的分治partition过程。任意挑一个元素，以该元素为支点，将数组分成两部分，左边是小于等于支点的，右边是大于支点的。如果左侧长度正好是(n－1)／2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位数在右侧，反之，中位数在左侧。进入相应的一侧继续寻找中位数。

//快速排序的分治过程找无序数组的中位数
int partition(int a[], int low, int high) //快排的一次排序过程
{
    int q = a[low];
    while (low < high)
    {
        while (low < high && a[high] >= q)
            high--;
        a[low] = a[high];
        while (low < high && a[low] <= q)
            low++;
        a[high] = a[low];
    }
    a[low] = q;
    return low;
}
int findMidium(int a[], int n)
{
    int index = n / 2;
    int left = 0;
    int right = n - 1;
    int q = -1;
    while (index != q)
    {
        q = partition(a, left, right);
        if (q < index)
            left = q + 1;
        else if (q>index)
            right = q - 1;
    }
    return a[index];
}

思路三：将数组的前（n+1）／2个元素建立一个最小堆。然后，对于下一个元素，和堆顶的元素比较，如果小于等于，丢弃之，如果大于，则用该元素取代堆顶，再调整堆，接着看下一个元素。重复这个步骤，直到数组为空。当数组都遍历完了，（堆中元素为最大的（n+1）／2个元素，）堆顶的元素即是中位数

 1 //构建最小堆找无序数组的中位数
 2 void nswap(int& i, int& j)
 3 {
 4     i = i^j;
 5     j = i^j;
 6     i = i^j;
 7 }
 8 void minHeapify(int a[], int i, int len)
 9 {
10     int temp;
11     int least = i;
12     int l = i * 2 + 1;
13     int r = i * 2 + 2;
14     if (l < len && a[l] < a[least])
15         least = l;
16     if (r < len && a[r] < a[least])
17         least = r;
18     if (least != i)
19     {
20         nswap(a[i], a[least]);
21         minHeapify(a, least, len);
22     }
23 }
24 void buildMinHeap(int a[], int len)
25 {
26     for (int i = (len-2) / 2; i >= 0; i--)
27     {
28         minHeapify(a, i, len);
29     }
30 }
31 int findMidium2(int a[], int n)
32 {
33     buildMinHeap(a, (n + 1) / 2);
34     for (int i = (n + 1) / 2; i < n; i++)
35     {
36         if (a[i] > a[0])
37         {
38             nswap(a[i], a[0]);
39             minHeapify(a, 0,(n + 1) / 2);
40         }        
41     }
42     return a[0];
43 }

----------------------------------------------------------

参考原文：https://blog.csdn.net/jiangyanting2011/article/details/70325215