列表排名算法

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）你可以看到.... :(