int BFPRT(int a[], int l, int r, int id) //求数组a下标l到r中的第id个数
{
if (r - l + 1 <= 5) //小于等于5个数,直接排序得到结果
{
insertionSort(a, l, r); return a[l + id - 1];
}
int t = l - 1; //当前替换到前面的中位数的下标
for (int st = l, ed; (ed = st + 4) <= r; st += 5) //每5个进行处理
{
insertionSort(a, st, ed); //5个数的排序
t++; swap(a[t], a[st+2]); //将中位数替换到数组前面,便于递归求取中位数的中位数
}
int pivotId = (l + t) >> 1; //l到t的中位数的下标,作为主元的下标
BFPRT(a, l, t, pivotId-l+1);//不关心中位数的值,保证中位数在正确的位置
int m = partition(a, l, r, pivotId), cur = m - l + 1;
if (id == cur) return a[m]; //刚好是第id个数
else if(id < cur) return BFPRT(a, l, m-1, id);//第id个数在左边
else return BFPRT(a, m+1, r, id-cur); //第id个数在右边
}