中值,顾名思义,就是指一个从小到大的序列的中间的那一个数。一般的讲,中值比平均值还要更加稳定。如一个序列中的某一个值被误乘以了100,平均值则会有很大的波动,但是中位数则不会发生太大的变化。
但是如果对数据先排序,然后再进行取中值,则比较耗时。以下是一种快速提取中位数的算法,算法描述如下:
1:取队首,队尾和中间的三个数,通过交换数据,使得队尾最大,中间的数据最小,队首的数据为哨兵。
2:交换中间和第2个数据,通过变换数据,使存在一个位置A,在该位置前的数据都小于哨兵,在该位置后的数据都大于或等于哨兵。
3:如果A的位置在队中之后,则更新队列为1~A,否则为A~end。并继续调用这个过程。
举例如下:
数组:3,6,2,1,9,8,0,4,5,7
经过步骤1并交换中间和第2个数的值之后,则为:
7,3,2,1,6,8,0,4,5,9;此序列中,7为哨兵
经过第一次迭代后,序列为:
4,3,2,1,6,5,0,7,8,9,此序列中,在数字7的位置是正确的。
第二次迭代则取1~7个数进行求解中位数,其中,哨兵为1。迭代之后如下:
0,1,2,3,6,5,4,7,8,9,同样的,此序列中,数字1的位置也是正确的。
第三次迭代则以第3~7个数进行求解,哨兵为5,此时,5即为中位数。
以下为非递归式调用的C代码。
int CQuickMedian(int * pnData, const int knLength)
{
int nLow = 0;
int nHigh = 0;
int nMiddle = 0;
int nMedian = 0;
int nLTmp = 0;
int nHTmp = 0;
nMedian = (knLength - 1) >> 1;
nHigh = knLength - 1;
while(1)
{
if(nHigh == nLow)
{
return pnData[nHigh];
}
if(nHigh == nLow + 1)
{
return pnData[nHigh] > pnData[nLow] ? pnData[nLow] : pnData[nHigh];
}
nMiddle = (nHigh + nLow)>>1;
if(pnData[nLow] > pnData[nHigh])
{
CSwap(&pnData[nHigh], &pnData[nLow]);
}
if(pnData[nMiddle] > pnData[nHigh])
{
CSwap(&pnData[nMiddle], &pnData[nHigh]);
}
if(pnData[nMiddle] > pnData[nLow])
{
CSwap(&pnData[nMiddle], &pnData[nLow]);
}
CSwap(&pnData[nMiddle], &pnData[nLow+1]);
nLTmp = nLow + 2;
nHTmp = nHigh - 1;
while(1)
{
while(pnData[nLTmp] <= pnData[nLow])
{
nLTmp ++;
}
while(pnData[nHTmp] >= pnData[nLow])
{
nHTmp --;
}
if(nLTmp > nHTmp)
{
CSwap(&pnData[nHTmp], &pnData[nLow]);
if(nHTmp > nMedian)
{
nHigh = nHTmp - 1;
}
else
{
nLow = nLTmp - 1;
}
break;
}
else
{
CSwap(&pnData[nLTmp], &pnData[nHTmp]);
nLTmp++;
nHTmp--;
}
}
}
}