0001 // 中位数算法蛮力版:效率低,仅适用于max(n1, n2)较小的情况 0002 template <typename T> //子向量S1[lo1, lo1 + n1)和S2[lo2, lo2 + n2)分别有序,数据项可能重复 0003 T trivialMedian ( Vector<T>& S1, int lo1, int n1, Vector<T>& S2, int lo2, int n2 ) { 0004 int hi1 = lo1 + n1, hi2 = lo2 + n2; 0005 Vector<T> S; //将两个有序子向量归并为一个有序向量 0006 while ( ( lo1 < hi1 ) && ( lo2 < hi2 ) ) { 0007 while ( ( lo1 < hi1 ) && S1[lo1] <= S2[lo2] ) S.insert ( S1[lo1 ++] ); 0008 while ( ( lo2 < hi2 ) && S2[lo2] <= S1[lo1] ) S.insert ( S2[lo2 ++] ); 0009 } 0010 while ( lo1 < hi1 ) S.insert ( S1[lo1 ++] ); 0011 while ( lo2 < hi2 ) S.insert ( S1[lo2 ++] ); 0012 return S[ ( n1 + n2 ) / 2]; //直接返回归并向量的中位数 0013 }