0001 template <typename T> //向量S1[lo1, lo1 + n1)和S2[lo2, lo2 + n2)分别有序,数据项可能重复 0002 T median ( Vector<T>& S1, int lo1, int n1, Vector<T>& S2, int lo2, int n2 ) { //中位数算法 0003 if ( n1 > n2 ) return median ( S2, lo2, n2, S1, lo1, n1 ); //确保n1 <= n2 0004 if ( n2 < 6 ) //递归基:1 <= n1 <= n2 <= 5 0005 return trivialMedian ( S1, lo1, n1, S2, lo2, n2 ); 0006 /////////////////////////////////////////////////////////////////////// 0007 // lo1 lo1 + n1/2 lo1 + n1 - 1 0008 // | | | 0009 // X >>>>>>>>>>>>>>> X >>>>>>>>>>>>>>> X 0010 // Y .. trimmed .. Y >>>>>>>>>>>>>>> Y >>>>>>>>>>>>>>> Y .. trimmed .. Y 0011 // | | | | | 0012 // lo2 lo2 + (n2-n1)/2 lo2 + n2/2 lo2 + (n2+n1)/2 lo2 + n2 -1 0013 /////////////////////////////////////////////////////////////////////// 0014 if ( 2 * n1 < n2 ) //若两个向量的长度相差悬殊,则长者(S2)的两翼可直接截除 0015 return median ( S1, lo1, n1, S2, lo2 + ( n2 - n1 - 1 ) / 2, n1 + 2 - ( n2 - n1 ) % 2 ); 0016 /////////////////////////////////////////////////////////////////////// 0017 // lo1 lo1 + n1/2 lo1 + n1 - 1 0018 // | | | 0019 // X >>>>>>>>>>>>>>>>>>>>> X >>>>>>>>>>>>>>>>>>>>> X 0020 // | 0021 // m1 0022 /////////////////////////////////////////////////////////////////////// 0023 // mi2b 0024 // | 0025 // lo2 + n2 - 1 lo2 + n2 - 1 - n1/2 0026 // | | 0027 // Y <<<<<<<<<<<<<<<<<<<<< Y ... 0028 // . 0029 // . 0030 // . 0031 // . 0032 // . 0033 // . 0034 // . 0035 // ... Y <<<<<<<<<<<<<<<<<<<<< Y 0036 // | | 0037 // lo2 + (n1-1)/2 lo2 0038 // | 0039 // mi2a 0040 /////////////////////////////////////////////////////////////////////// 0041 int mi1 = lo1 + n1 / 2; 0042 int mi2a = lo2 + ( n1 - 1 ) / 2; 0043 int mi2b = lo2 + n2 - 1 - n1 / 2; 0044 if ( S1[mi1] > S2[mi2b] ) //取S1左半、S2右半 0045 return median ( S1, lo1, n1 / 2 + 1, S2, mi2a, n2 - ( n1 - 1 ) / 2 ); 0046 else if ( S1[mi1] < S2[mi2a] ) //取S1右半、S2左半 0047 return median ( S1, mi1, ( n1 + 1 ) / 2, S2, lo2, n2 - n1 / 2 ); 0048 else //S1保留,S2左右同时缩短 0049 return median ( S1, lo1, n1, S2, mi2a, n2 - ( n1 - 1 ) / 2 * 2 ); 0050 }