中位数问题

求中位数

中位数（Median）是将一组数从小到大排好后居中的数；如果这一组数的个数为奇数，那么中位数是存在的；但若个数为偶数，就没有中间的那一个数了，因此取居中两个数的平均数。例如，3,1,7,5,9经过排列后是1,3,5,7,9，所以中位数是5；但3,1,7,5,9,4经过排列得到1,3,4,5,7,9，所以中位数就是(4+5)/2=4。为了方便，用整数计算，编写一个程序，接收一个整数数组，找出该数组的中位数。
注：原题要求此题不排序，但受评测系统限制，这里不作此要求，大家可以使用排序。

Input

第一行只有一个整数T（0＜T≤10），表示共有T组测试数据。接下来每两行描述一组测试数据：
第一行只有一个整数n（0＜n≤1000），表示该测试数据的数列长度为n（个元素）。第二行共n个小于10000的非负整数，为数列所有元素。

Output

共T行，每行输出一个整数，第k行输出的整数为第k组测试数据的结果（中位数）。

----------------解决方案--------------------------------------------------------
挺难的,特别是这句:第一行只有一个整数n（0＜n≤1000），表示该测试数据的数列长度为n（个元素）。第二行共n个小于10000的非负整数，为数列所有元素。
======因为不知道各组长度,这样给内存动态分配增加了难度.数据结构我学得不深入,尝试写一下.
----------------解决方案--------------------------------------------------------

汗 大虾加油搞....
搞好了通知小弟~~~

----------------解决方案--------------------------------------------------------
2楼的呵呵
你可以用数组的

不过就10000个空间
浪费就浪费点吧

----------------解决方案--------------------------------------------------------

动态数组就好了，不然太浪费

----------------解决方案--------------------------------------------------------
动态数组？？
还没有听说过
动态数组是什么啊
不会是链表吧
----------------解决方案--------------------------------------------------------
malloc(size)...不会没听说过吧...
----------------解决方案--------------------------------------------------------

下面还要求每一个组输入一个不同的长度的数组,难道每一个数组还定义多少个固定数值吗?这样的话空间就太浪费了,假如数据更大的话,西西``后果就可能严重了.
----------------解决方案--------------------------------------------------------