0001 template <typename T> //ϣ 0002 void Vector<T>::shellSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size <= 2^30 0003 for ( int d = 0x3FFFFFFF; 0 < d; d >>= 1 ) //PS Sequence: { 1, 3, 7, 15, ..., 1073741823 } 0004 for ( int j = lo + d; j < hi; j++ ) { //for each j in [lo+d, hi) 0005 T x = _elem[j]; int i = j - d; 0006 while ( lo <= i && _elem[i] > x ) 0007 { _elem[i + d] = _elem[i]; i -= d; } 0008 _elem[i + d] = x; //insert [j] into its subsequence 0009 } 0010 }