做PAT基础编程题目集6-11求自定类型元素序列的中位数收获(含动画解析)
做PAT基础编程题目集6-11求自定类型元素序列的中位数收获
·题目概要
初来乍到,多多包涵。
题目网址:https://pintia.cn/problem-sets/14/problems/743
题目内容:
6-11 求自定类型元素序列的中位数 (25 分)本题要求实现一个函数,求N个集合元素A[]的中位数,即序列中第⌊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;
}
/* 你的代码将被嵌在这里 */
相信很多小伙伴做这道题的时候总是第5个测试点过不去,第五个测试点是:大N卡时。
我也是提交了很多次,很多方法都用过了,但是还是没过去第五关。
经典的方法:冒泡法,二排法,快排法。在网上了解了原理,自己写了程序,不知道是不是代码写得太烂了而没过。
为解这道题,还自创了排除的方法。
方法如下:创建另一个数组B,B初始值为0,用for循环在A数组依次找出最小的数,B依次记录A数组中较小的值,对应的值改为“1”直到统计了一半个数的“1”终止,输出没有排除的数组A中的最小的元素。
歪点子不说了,下面进入正题,通过搜索,搜到了一个正确答案。
·分享图解流程图(希尔排序)
ElementType Median( ElementType A[], int N)
{
int i, j, Increment;
ElementType Tmp;
//将数组排序
for ( Increment = N / 2; Increment > 0; Increment /= 2){
for ( i = Increment; i < N; i++){
Tmp = A[ i ];
for (j = i;j >= Increment;j -= Increment ){
if ( Tmp < A[ j - Increment ])
A[ j ] = A[ j - Increment ];
else
break;
}
A[ j ] = Tmp;
}
}
return A[ N / 2 ];
}
---------------------
作者:code_monky
来源:****
原文:https://blog.****.net/Peterclass/article/details/51973906
本人只是把对于这个程序的理解分享出来,本人并非该程序作者。其实直到现在,个人对于希尔排序还是感觉比较神奇的。
进入正题:首先,这个程序对要排列的数组做了什么呢?
其实一开始看到这段代码,也没啥头绪,3层循环,光看代码的话脑子是乱的。调试的话也不容易,也难以看懂内部的程序结构,至于原作者怎么想的也是糊里糊涂的。
首先,上百度查希尔算法,大致知道先是分成简单的组,简单地排成大致有序的样子,然后缩减分组,
上图绿色的框内为注释,如果看不清的话尝试放大图片。
这个程序运行的时候的监视情况(raptor内):
单单看上面的监视的话还是非常难看出这个程序究竟在干嘛的,不看个十几遍是看不懂这个程序究竟在干嘛的。
我在看过N遍之后终于看明白了。
为了方便大家的的理解,为此,我专门做了动画方便大家理解这个程序在干嘛。
请欣赏(我相信做的还是可以的):
以上是最外层循环循环第一遍所发生的事。
i的初始值为4,然后依次增加,A[i]依次和A[i-4]比较,i直到加到7,比较结束,不符合升序的就调换位置(相互交换数值)。
数值也由原来的41682735变成了21354768。
第二趟动画演示:
i的初始值为2,然后依次增加,A[i]依次和A[i-2]比较,(也就是[i-Increment])i直到加到7,比较结束,不符合升序的就调换位置(相互交换数值)。【这个数据比较特殊,一路绿灯呢,我要是没做动画我还没发现呢】
第三趟动画演示:
i的初始值为1,然后依次增加,A[i]依次和A[i-1]比较,i直到加到7,比较结束,不符合升序的就调换位置(相互交换数值)。
所以,总的过程是这样的:
(由于我所用的数据比较巧了,所以第二次缩减增量时一路绿灯,有兴趣的朋友可以多举几个例子试试)
虽然不知道希尔算法是怎么推出来的,但是也知道了这个算法的运作过程了,可以看到,这个程序一趟比一趟更接近升序的排列。
附希尔排序的一个比较详细的博文:https://blog.****.net/MoreWindows/article/details/6668714
最后,送上动画的花絮(没错,是3d的):