PTA基础编程题目集 6-11 求自定类型元素序列的中位数（C语言实现）

题目描述

摘要：本文介绍如何实现求自定义类型元素序列的中位数，核心思路是先降序排序（希尔排序），再取下标 (N-1)/2 的元素，时间复杂度约 O(N^1.3)，空间 O(1)。文末附完整代码及测试用例。

本题要求实现一个函数，求 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

函数部分实现

/* 快速选择后返回中位数 */
ElementType Median( ElementType A[], int N )
{
int i, j, gap;
ElementType temp;

/* 希尔排序（降序）：时间复杂度约 O(N^1.3)，可通过大 N 时限 */
for (gap = N / 2; gap > 0; gap /= 2) { /* 增量序列：每次折半 */
for (i = gap; i < N; i++) { /* 从 gap 开始向后扫描 */
temp = A[i]; /* 暂存当前元素 */
/* 降序插入：若前一个增量位置的元素更小，则后移 */
for (j = i; j >= gap && A[j – gap] < temp; j -= gap)
A[j] = A[j – gap];
A[j] = temp; /* 放入正确位置 */
}
}

/* 降序排列后，A[(N-1)/2] 恰好是第 ⌊(N+1)/2⌋ 大的元素 */
return A[(N – 1) / 2];
}

下面是 Median 函数的算法流程图：

#mermaid-svg-VT49DHEsesRFaykU{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-VT49DHEsesRFaykU .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-VT49DHEsesRFaykU .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-VT49DHEsesRFaykU .error-icon{fill:#552222;}#mermaid-svg-VT49DHEsesRFaykU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-VT49DHEsesRFaykU .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-VT49DHEsesRFaykU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-VT49DHEsesRFaykU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-VT49DHEsesRFaykU .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-VT49DHEsesRFaykU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-VT49DHEsesRFaykU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-VT49DHEsesRFaykU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-VT49DHEsesRFaykU .marker.cross{stroke:#333333;}#mermaid-svg-VT49DHEsesRFaykU svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-VT49DHEsesRFaykU p{margin:0;}#mermaid-svg-VT49DHEsesRFaykU .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-VT49DHEsesRFaykU .cluster-label text{fill:#333;}#mermaid-svg-VT49DHEsesRFaykU .cluster-label span{color:#333;}#mermaid-svg-VT49DHEsesRFaykU .cluster-label span p{background-color:transparent;}#mermaid-svg-VT49DHEsesRFaykU .label text,#mermaid-svg-VT49DHEsesRFaykU span{fill:#333;color:#333;}#mermaid-svg-VT49DHEsesRFaykU .node rect,#mermaid-svg-VT49DHEsesRFaykU .node circle,#mermaid-svg-VT49DHEsesRFaykU .node ellipse,#mermaid-svg-VT49DHEsesRFaykU .node polygon,#mermaid-svg-VT49DHEsesRFaykU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-VT49DHEsesRFaykU .rough-node .label text,#mermaid-svg-VT49DHEsesRFaykU .node .label text,#mermaid-svg-VT49DHEsesRFaykU .image-shape .label,#mermaid-svg-VT49DHEsesRFaykU .icon-shape .label{text-anchor:middle;}#mermaid-svg-VT49DHEsesRFaykU .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-VT49DHEsesRFaykU .rough-node .label,#mermaid-svg-VT49DHEsesRFaykU .node .label,#mermaid-svg-VT49DHEsesRFaykU .image-shape .label,#mermaid-svg-VT49DHEsesRFaykU .icon-shape .label{text-align:center;}#mermaid-svg-VT49DHEsesRFaykU .node.clickable{cursor:pointer;}#mermaid-svg-VT49DHEsesRFaykU .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-VT49DHEsesRFaykU .arrowheadPath{fill:#333333;}#mermaid-svg-VT49DHEsesRFaykU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-VT49DHEsesRFaykU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-VT49DHEsesRFaykU .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-VT49DHEsesRFaykU .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-VT49DHEsesRFaykU .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-VT49DHEsesRFaykU .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-VT49DHEsesRFaykU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-VT49DHEsesRFaykU .cluster text{fill:#333;}#mermaid-svg-VT49DHEsesRFaykU .cluster span{color:#333;}#mermaid-svg-VT49DHEsesRFaykU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-VT49DHEsesRFaykU .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-VT49DHEsesRFaykU rect.text{fill:none;stroke-width:0;}#mermaid-svg-VT49DHEsesRFaykU .icon-shape,#mermaid-svg-VT49DHEsesRFaykU .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-VT49DHEsesRFaykU .icon-shape p,#mermaid-svg-VT49DHEsesRFaykU .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-VT49DHEsesRFaykU .icon-shape .label rect,#mermaid-svg-VT49DHEsesRFaykU .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-VT49DHEsesRFaykU .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-VT49DHEsesRFaykU .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-VT49DHEsesRFaykU :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

是

是

否

否

否

开始 Median(A, N)

gap = N / 2

gap > 0 ?

i = gap

i < N ?

temp = A[i]; j = i

j >= gap 且 A[j-gap] < temp ?

A[j] = A[j-gap]; j -= gap

A[j] = temp; i++

gap /= 2

返回 A[(N-1)/2]

结束

代码部分实现

/* 6-11 求自定类型元素序列的中位数
* 题目：实现函数 Median(A[], N)，返回 N 个元素的中位数。
* 实现原理：先排序再取中间元素。
* 这里用希尔排序把数组降序排列，
* 排序后中位数位于下标 (N-1)/2（向下取整，
* 对奇数/偶数长度都适用，偶数时取中间偏左者）。
* 时间复杂度 O(N^1.3)（希尔），空间复杂度 O(1)。
*/
#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;
}

/* 希尔排序（降序）后返回中位数 */
ElementType Median( ElementType A[], int N )
{
int i, j, gap;
ElementType temp;

/* 希尔排序（降序）：时间复杂度约 O(N^1.3)，可通大 N 时限 */
for (gap = N / 2; gap > 0; gap /= 2) { /* 增量序列：每次折半 */
for (i = gap; i < N; i++) { /* 从 gap 开始向后扫描 */
temp = A[i]; /* 暂存当前元素 */
/* 降序插入：若前一个增量位置的元素更小，则后移 */
for (j = i; j >= gap && A[j – gap] < temp; j -= gap)
A[j] = A[j – gap];
A[j] = temp; /* 放入正确位置 */
}
}

/* 降序排列后，A[(N-1)/2] 恰好是第 ⌊(N+1)/2⌋ 大的元素 */
return A[(N – 1) / 2];
}