该算法基于 chmike 的算法,但重新排序索引的向量为const
。这个功能和他的11个都一致! [0..10] 的排列。复杂度为 O(N^2),以 N 为输入的大小,或者更准确地说,最大的大小orbit.
请参阅下文,了解修改输入的优化 O(N) 解决方案。
template< class T >
void reorder(vector<T> &v, vector<size_t> const &order ) {
for ( int s = 1, d; s < order.size(); ++ s ) {
for ( d = order[s]; d < s; d = order[d] ) ;
if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );
}
}
这是我投入更多精力的 STL 风格版本。它大约快了 47%(也就是说,几乎是 [0..10] 的两倍!),因为它尽早完成所有交换,然后返回。重新排序向量由多个轨道组成,每个轨道在到达其第一个成员时都会重新排序。当最后几个元素不包含轨道时,速度会更快。
template< typename order_iterator, typename value_iterator >
void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v ) {
typedef typename std::iterator_traits< value_iterator >::value_type value_t;
typedef typename std::iterator_traits< order_iterator >::value_type index_t;
typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
diff_t remaining = order_end - 1 - order_begin;
for ( index_t s = index_t(), d; remaining > 0; ++ s ) {
for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;
if ( d == s ) {
-- remaining;
value_t temp = v[s];
while ( d = order_begin[d], d != s ) {
swap( temp, v[d] );
-- remaining;
}
v[s] = temp;
}
}
}
最后,为了一劳永逸地回答这个问题,一个变体确实破坏了重新排序向量(用-1填充它)。对于 [0..10] 的排列,它比之前的版本快约 16%。因为覆盖输入可以实现动态编程,所以它是 O(N),对于某些序列较长的情况渐近更快。
template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v ) {
typedef typename std::iterator_traits< value_iterator >::value_type value_t;
typedef typename std::iterator_traits< order_iterator >::value_type index_t;
typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
diff_t remaining = order_end - 1 - order_begin;
for ( index_t s = index_t(); remaining > 0; ++ s ) {
index_t d = order_begin[s];
if ( d == (diff_t) -1 ) continue;
-- remaining;
value_t temp = v[s];
for ( index_t d2; d != s; d = d2 ) {
swap( temp, v[d] );
swap( order_begin[d], d2 = (diff_t) -1 );
-- remaining;
}
v[s] = temp;
}
}