做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的)：