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

题目描述摘要本文介绍如何实现求自定义类型元素序列的中位数核心思路是先降序排序希尔排序再取下标 (N-1)/2 的元素时间复杂度约 O(N^1.3)空间 O(1)。文末附完整代码及测试用例。本题要求实现一个函数求 N 个集合元素 A[] 的中位数即序列中第 ⌊(N1)/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 ( i0; iN; i ) scanf(%f, A[i]); printf(%.2f\n, Median(A, N)); return 0; } /* 你的代码将被嵌在这里 */输入样例3 12.3 34 -5输出样例12.30函数部分实现/* 快速选择后返回中位数 */ElementTypeMedian(ElementType A[],intN){inti,j,gap;ElementType temp;/* 希尔排序降序时间复杂度约 O(N^1.3)可通过大 N 时限 */for(gapN/2;gap0;gap/2){/* 增量序列每次折半 */for(igap;iN;i){/* 从 gap 开始向后扫描 */tempA[i];/* 暂存当前元素 *//* 降序插入若前一个增量位置的元素更小则后移 */for(ji;jgapA[j-gap]temp;j-gap)A[j]A[j-gap];A[j]temp;/* 放入正确位置 */}}/* 降序排列后A[(N-1)/2] 恰好是第 ⌊(N1)/2⌋ 大的元素 */returnA[(N-1)/2];}下面是 Median 函数的算法流程图是是是否否否开始 Median(A, N)gap N / 2gap 0 ?i gapi N ?temp A[i]; j ij gap 且 A[j-gap] temp ?A[j] A[j-gap]; j - gapA[j] temp; igap / 2返回 A[(N-1)/2]结束代码部分实现/* 6-11 求自定类型元素序列的中位数 * 题目实现函数 Median(A[], N)返回 N 个元素的中位数。 * 实现原理先排序再取中间元素。 * 这里用希尔排序把数组降序排列 * 排序后中位数位于下标 (N-1)/2向下取整 * 对奇数/偶数长度都适用偶数时取中间偏左者。 * 时间复杂度 O(N^1.3)希尔空间复杂度 O(1)。 */#includestdio.h#defineMAXN10typedeffloatElementType;ElementTypeMedian(ElementType A[],intN);intmain(){ElementType A[MAXN];intN,i;scanf(%d,N);for(i0;iN;i)scanf(%f,A[i]);printf(%.2f\n,Median(A,N));return0;}/* 希尔排序降序后返回中位数 */ElementTypeMedian(ElementType A[],intN){inti,j,gap;ElementType temp;/* 希尔排序降序时间复杂度约 O(N^1.3)可通大 N 时限 */for(gapN/2;gap0;gap/2){/* 增量序列每次折半 */for(igap;iN;i){/* 从 gap 开始向后扫描 */tempA[i];/* 暂存当前元素 *//* 降序插入若前一个增量位置的元素更小则后移 */for(ji;jgapA[j-gap]temp;j-gap)A[j]A[j-gap];A[j]temp;/* 放入正确位置 */}}/* 降序排列后A[(N-1)/2] 恰好是第 ⌊(N1)/2⌋ 大的元素 */returnA[(N-1)/2];}