PTA求自定类型元素序列的中位数

素颜马尾好姑娘i 2022-06-01 08:35 78阅读 0赞

#### 6-11 求自定类型元素序列的中位数（25 分） ####

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

### 函数接口定义： ###

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

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

### 裁判测试程序样例： ###

### 输入样例： ###

3
    12.3 34 -5

### 输出样例： ###

12.3

#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;
    }
    
    /* 你的代码将被嵌在这里 */
    
    //堆调整，构建大顶堆，arr[]是待调整的数组，i是待调整的数组
    //元素的位置，length是数组的长度
    void HeapAdjust(ElementType a[], int i, int length)
    {
        int Child;
        ElementType temp;
        for(; 2 * i + 1 < length; i = Child)
        {
            //子节点的位置 = 2 * (parent(父结点)) + 1
            Child = 2 * i + 1;
            //得到子结点中较大的结点
            if(Child < length - 1 && a[Child + 1] > a[Child])
                Child++;
            //如果较大的子结点大于父结点那么把较大的子结点往上移动
            //替换它的父结点
            if(a[i] < a[Child])
            {
                temp = a[i];
                a[i] = a[Child];
                a[Child] = temp;
            }
            else
                break;
        }
    }
    //堆排序算法
    void HeapSort(ElementType a[], int length)
    {
        int i;
        ElementType temp;
        //调整序列的前半部分元素，调整完之后第一个元素
        //是序列的最大元素，length/2-1是最后一个非叶子结点
        for(i = length/2 - 1; i >= 0; --i)
            HeapAdjust(a, i, length);
        //从最后一个元素开始对序列进行调整，不断的缩小调整
        //的范围直到第一个元素
        //循环里是把第一个元素和当前的最后一个元素交换
        //保证当前的最后一个位置的元素是现在这个序列的最大的
        //不断的缩小调整heap的范围，每一次调整完毕保证第一个
        //元素是当前序列的最大的元素
        for(i = length - 1; i > 0; --i)
        {
            temp=a[i];
            a[i]=a[0];
            a[0]=temp;
    
            HeapAdjust(a, 0, i);                      //递归调整
        }
    }
    ElementType Median( ElementType A[], int N )
    {
        HeapSort(A,N);
        return A[N/2];
    }