本文主要是介绍中位数的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">参照王晓东的算法设计</span>中位数的中位数，即将一串数分成n段，求其排好序了的中间那个数，再把这些所有中位数再求一次中位数。
for(int i = 0; i <= (r-p-4)/5; i++){ quickSort(a, p+5*i, p+5*i+4); //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置 Swap(a[p+5*i+2],a[p+i]); }//找中位数的中位数，r-p-4即上面所说的n-5 int x = lineSelect(a,p,p+(r-p-4)/5,(r-p-4)/10);
线性查找第k小的数的核心代码
//按中位数的中位数x划分，并返回x的下标
int partition(int a[],int p,int r,int x)
{ int i = p,j = r + 1; while(true) { while(a[++i]<x && i<r); while(a[--j]>x); if(i>=j) { break; } Swap(a[i],a[j]); } return j;
} int lineSelect(int * a,int p, int r, int k)
{if(r - p < 75){//排序quickSort(a, p, r); return a[p+k-1]; }for(int i = 0; i <= (r-p-4)/5; i++){ quickSort(a, p+5*i, p+5*i+4); //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置 Swap(a[p+5*i+2],a[p+i]); }//找中位数的中位数，r-p-4即上面所说的n-5 int x = lineSelect(a,p,p+(r-p-4)/5,(r-p-4)/10);int i = partition(a,p,r,x);int j = i - p + 1;if(k <= j)return lineSelect(a,p,i,k);elsereturn lineSelect(a,i+1,r,k-j);
}这篇关于中位数的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
