fig07_21.cpp

来自「经典书籍源代码啊。。。第三版。。。数据结构与算法分析——C++描述(第3版).」· C++ 代码 · 共 27 行

template <typename Comparable>
void largeObjectSort( vector<Comparable> & a )
{
    vector<Pointer<Comparable> > p( a.size( ) );
    int i, j, nextj;

    for( i = 0; i < a.size( ); i++ )
        p[ i ] = &a[ i ];

    quicksort( p );

        // Shuffle items in place
    for( i = 0; i < a.size( ); i++ )
        if( p[ i ] != &a[ i ] )
        {
            Comparable tmp = a[ i ];
            for( j = i; p[ j ] != &a[ i ]; j = nextj )
            {
                nextj = p[ j ] - &a[ 0 ];
                a[ j ] = *p[ j ];
                p[ j ] = &a[ j ];
            }
            a[ j ] = tmp;
            p[ j ] = &a[ j ];
        }
}