Liste algorithme de classement

Question

Étant donné une liste de numéros, ce qui peut être dans un ordre quelconque, comme

3, -5, -1, 2, 7, 12, -8 

Je voudrais produire une liste qui représente leur rang, qui dans ce cas serait

4, 1, 2, 3, 5, 6, 0 

Les nombres sont en réalité des membres d'une liste ordonnée de classes. Notez que l'ordre de la liste ne change pas, ils sont comptabilisés en fonction de leur classement.

(ces chiffres représentent un ordre z, mais il pourrait y avoir d'autres utilisations)

Answer 1

C'est ma solution, non testé pour l'instant:

// this will be our storage of the new z-order 
int *tmpZ = new int[GetCount()]; 

int currentZ = INT_MIN; 
int smallestIdx = -1; 
int newZ = 0; 
for (int passes = 0; passes < GetCount(); passes++) 
{ 
    int smallestZ = INT_MAX; 
    // find the index of the next smallest item 
    for (int i = 0; i < GetCount(); i++) 
    { 
     if (GetAt(i)->m_zOrder > currentZ && GetAt(i) < smallestZ) 
     { 
      smallestIdx = i; 
      smallestZ = GetAt(i)->m_zOrder; 
     } 
    } 
    tmpZ[smallestIdx] = newZ; 

    // prepare for the next item 
    currentZ = smallestZ; 
    newZ++; 
    smallestIdx = -1; 
} 

// push the new z-order into the array 
for (int i = 0; i < GetCount(); i++) 
    GetAt(i)->m_zOrder = tmpZ[i]; 

Il est O (n^2), comme vous pouvez le voir .... :(