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

2018-06-18 04:00:27来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

函数接口定义:

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

其中给定集合元素存放在数组A[]中,正整数N是数组元素个数。该函数须返回NA[]元素的中位数,其值也必须是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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言实现斐波那契数列(非递归)

下一篇:4-10 阶乘计算升级版 (20分)