例：求自定类型元素序列的中位数

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

/* 你的代码将被嵌在这里 */
输入样例：
3
12.3 34 -5
输出样例：
12.30

希尔排序算法代码：

ElementType Median( ElementType A[], int N )
{
	ElementType temp;
	int gap,i,j;
	for(gap=N/2;gap>0;gap/=2)//步长设置为2 
	{
		for(i=gap;i<N;i++)//相当于在同一组内采用插入排序 
		{
			for(j=i-gap;j>=0 && A[j]>A[j+gap];j-=gap)//比较、交换 
			{
				temp=A[j];
				A[j]=A[j+gap];
				A[j+gap]=temp;
			}
		}
	}
	return A[N/2];//返回中间元素 
 }

希尔排序是不稳定的。
希尔排序的时间复杂度与增量序列的选取有关，取值大约为O(n^(1.3—2))。
希尔排序的时间复杂度会比o(n^2)好一些。