列表排名算法

Question

鉴于号的列表，它可以是任何顺序，如

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

我想产生代表自己的排名，列出在这种情况下将

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

这些数字实际上是有序类列表的一部分。请注意，列表的顺序不会改变，他们只是根据他们的等级来计算。

（这些数字代表的z顺序，但也可能有其他用途）

Answer 1

这是我的解决方案，未经测试作为尚未：

// 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]; 

这是O（n^2）你可以看到.... :(