4-11 求自定类型元素序列的中位数 (25分)

本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第\lfloor N/2 +1\rfloor?N/2+1?大的元素。其中集合元素的类型为自定义的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

解题的过程及感想：
呼，经过好几次的修改，终于改出来了（有点小激动）。这个题目看似简单，实则暗藏陷阱。这个题目的思路很简单：排序，然后返回值。只要排序完成，题目基本上就解决啦。
做这个题目的时候，像我这种对算法不是特别了解的，就只能默默的使用冒泡排序啦，但是老是过不了，显示超时。运用强大的百度，又分别用了快速排序算法和希尔排序算法

快速排序算法（依然显示超时）

void Q_sort(ElementType A[],int N)
{
    int i=0,j=N-1;
    ElementType key = A[0];
    if(N>1)
    {
        while(i<j)
        {
            while(i<j&&A[j]>key)
                j--;
            if(i<j)
                A[i++] = A[j];
            while(i<j&&A[i]<key)
                i++;
            if(i<j)
                A[j--] = A[i];
        }
        A[i] = key;
        Q_sort(A,i);
        Q_sort(A+i+1,N-i-1);
    }
}

希尔排序算法（成功解决问题）：

void ShellSort(ElementType a[],int n)
{
    int i,j,dk;
    ElementType tmp;
    for(dk=n/2; dk>0; dk/=2)
        for(i=dk; i<n; i++)
        {
            tmp=a[i];
            for(j=i; j>=dk; j-=dk)
                if(tmp<a[j-dk])
                    a[j]=a[j-dk];
                else break;
            a[j]=tmp;
        }
}

ElementType Median( ElementType A[], int N )
{
    // Q_sort(A,N);
    ShellSort(A,N);
    return A[N/2];
}

排序算法的讲解：http://blog.csdn.net/zhangjikuan/article/details/49095533

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有