0001 template <typename T> //向量希尔排序
0002 void Vector<T>::shellSort( Rank lo, Rank hi ) { // 0 <= lo < hi <= size <= 2^31
0003    for ( Rank d = 0x7FFFFFFF; 0 < d; d >>= 1 ) // PS Sequence: { 1, 3, 7, 15, 31, ... }
0004       for ( Rank j = lo + d; j < hi; j++ ) { // for each j in [lo+d, hi)
0005          T x = _elem[j]; Rank i = j; // within the prefix of the subsequence of [j]
0006          while ( ( lo + d <= i ) && ( x < _elem[i - d] ) ) // find the appropriate
0007             _elem[i] = _elem[i - d], i -= d; // predecessor [i]
0008          _elem[i] = x; // where to insert [j]
0009       }
0010 }