0001 template <typename T> //向量S1[lo1, lo1 + n1)和S2[lo2, lo2 + n2)分别有序，数据项可能重复 0002 T median ( Vector<T>& S1, Rank lo1, Rank n1, Vector<T>& S2, Rank lo2, Rank 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 Rank mi1 = lo1 + n1 / 2; 0042 Rank mi2a = lo2 + ( n1 - 1 ) / 2; 0043 Rank 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 }