6-11 求自定类型元素序列的中位数

本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第$[(N+1)/2]$大的元素。其中集合元素的类型为自定义的ElementType。

函数接口定义

ElementType Median( ElementType A[], int N );

其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。

裁判测试程序样例

#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Median( ElementType A[], int N );

int main ()
{
    ElementType A[MAXN];
    int N, i;

    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &A[i]);
    printf("%.2f\n", Median(A, N));

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例

3
12.3 34 -5

输出样例

12.30

分析及答案

这道题的思路是比较直接的，先对序列进行排序，然后输出排序后的序列中间位置的元素即可。

但是这道题的测试点中是有大N的，$O(n^2)$的冒泡排序会导致运行超时。因此，下面的程序会使用$O(n\log n)$的归并排序。归并排序涉及到递归，如果将执行过程以树的形式手画出来会好理解很多，在递归传递函数的时候也要注意下标移动的问题。

//采用递归的归并排序尝试解决大N卡时间问题

//合并函数，将两个数组合并到一个
void merge (ElementType *a, int l, int mid, int r, ElementType *c) {
    int i=l, k=mid+1, pos=l;
    while (i<=mid && k<=r) {
        //两个指针，谁小就把谁放进数组里，然后往后移动对应的指针
        if (a[k] <= a[i]) {
            c[pos]=a[k];
            k++;
        }
        else {
            c[pos]=a[i];
            i++;
        }
        pos++;
    }
    //把剩余的序列元素全部放到数组里，因为while退出条件的限制，这两条for循环必然只有一条会执行
    for (;i<=mid;i++,pos++) c[pos]=a[i];
    for (;k<=r;k++,pos++) c[pos]=a[k];
}

void mergeSort (ElementType A[], int l, int r, ElementType *tmp){
    if (l>=r)
        //左右位置重合，停止分解
        return;
    int mid = (r+l)/2;
    //递归，直到l与mid，mid与r相邻
    mergeSort(A,l,mid,tmp);
    mergeSort(A,mid+1,r,tmp);
    //合并
    merge (A,l,mid,r,tmp);
    for (int i=l;i<=r;i++)
        A[i]=tmp[i];
}

ElementType Median(ElementType A[], int N ) {
    //创建一个和排序数组一样大的temp数组进行合并
    ElementType tmp[N];
    mergeSort (A,0,N-1,tmp);
    int mid;
    return A[N/2];
}