algorithm - 列表排名算法

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).... :(