用二分法，一般求数组中第k小的数常用该算法 :)
效率是很高的，特别是你的题目要求，N还是很小的
在毫秒级瞬间就可以完成计算的
思路是这样的：
在数组中随机找个数做中点（一般可拿数组中第一个数，或者产生一个随机数），然后从左到右遍历一遍数组，比该中点数小的放左边，比该中点数大的放右边，然后判断此时中点数的位置p，如果p<k，那么第k小的数肯定在右边，递归在右边那串数中查找第(k-p)小的数；如果p>k，那么第k小的数肯定在左边，递归在左边那串数中查找第k小的数
程序如下：
//以数组array[left]为中点，比其小的放左边，比其大的放右边，array[left]这个元素最后位置在array[middle]
int Partition(int array[],int left, int right)
{
int pivot=X[left];
int middle;
int L=left;
int R=right;
int tmp;
while (L<R)
{
while (arrya[L]<=pivot && L<=right) L++;
while (array[R]>pivot && R>=left) R--;
if (L<R)
{
tmp=array[L];
array[L]=array[R];
array[R]=tmp;
}
}
middle=R;
tmp=array[left];
array[left]=array[middle];
array[middle]=tmp;
return middle;
}
//在array[left]到array[right]里查找第k小的数，将该数返回
int select(int array[], int left, int right, int k)
{
int middle;
if (left==right) return left;
middle=Partition(array,left,right);
if (middle-left+1>=k) return select(array,left,middle,k);
else return select(array,middle+1,right,k-(middle-left+1));
}
温馨提示：答案为网友推荐，仅供参考