代码之家 › 专栏 › 技术社区 › Nick

列表排序算法[重复]

ranking sorting algorithm

Nick · 技术社区 · 17 年前

给出一个数字列表,可以按任意顺序排列,例如

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

我想列出一份代表他们级别的名单,在这种情况下

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

(这些数字表示z阶,但可能还有其他用途)

1 回复 | 直到 13 年前

Nick 17 年前

这是我的解决方案,尚未测试:

// 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),如你所见。。。。:(

推荐文章