6-11 求自定类型元素序列的中位数（25 分）
本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第⌊N/2+1⌋大的元素。其中集合元素的类型为自定义的ElementType。
函数接口定义：
1
| ElementType Median( ElementType A[], int N );
|
其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。
裁判测试程序样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #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;
}
|
输入样例：
输出样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
void shell_sort(ElementType A[],int N);
ElementType Median(ElementType A[],int N)
{
if(N==1)
return A[0];
shell_sort(A,N);
return A[N/2];
}
void shell_sort(ElementType A[],int N)
{
int i,j,gap;
for(gap=N/2;gap>0;gap/=2)
for(i=gap;i<N;i++)
for(j=i-gap;j>=0&&A[j]>A[j+gap];j-=gap)
{
ElementType temp=A[j];
A[j]=A[j+gap];
A[j+gap]=temp;
}
}
|
