正如我们建议的那样，你可以只对索引进行排序（使用比较器函数，根据索引处的原始数组），然后用一个O（n）函数在置换后的索引中循环检查奇偶性。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool parity( const vector<int> &V )    // returns true for even, false for odd
{                                      // V is a permutation of 0, 1, ..., n-1 (NOTE: zero-based!)
   vector<bool> visited( V.size(), false );
   bool result = true;
   for ( int start = 0; start < V.size(); start++ )
   {
      if ( visited[start] ) continue;
      visited[start] = true;
      for ( int j = V[start]; j != start; j = V[j] )
      {
         result = !result;
         visited[j] = true;
      }
   }
   return result;
}

int main()
{
   vector<int> test = { { 17, 0, 19, 13, 4, -5, -6, 27, -31 } };

   vector<int> indices( test.size() );   iota( indices.begin(), indices.end(), 0 );
   sort( indices.begin(), indices.end(), [&test]( int i, int j ){ return test[i] < test[j]; } );
                   
   cout << "Sorted array: ";
   for ( int i : indices ) cout << test[i] << " ";
   cout << "\nParity: " << ( parity( indices ) ? "even" : "odd" ) << '\n';
}

Sorted array: -31 -6 -5 0 4 13 17 19 27 
Parity: odd