c++ - 冒泡排序算法不起作用

Question

我正在创建 C++/SFML 游戏引擎。游戏中的每个“实体”都有一个指向它的指针，存储在实体类的静态 vector 中，称为 entityRenderList。该 vector 在游戏循环的每次迭代中由冒泡排序算法排序，以便以正确的顺序绘制 Sprite 。

每当删除一个实体时，它都会用 NULL 指针替换它在 vector 中的指针。默认情况下，我的算法应该将它找到的所有 NULL 指针排序到 vector 的后面，然后将它们从那里删除。

这里是排序算法的代码:

bool Entity::depthSortFunction(Entity* a, Entity* b)
{
    if (b==NULL) return false; //any NULL values are moved to the back
    if (a==NULL) return true;

    else return (a->depth_) < (b->depth_);
}

void Entity::sortEntityRenderList()
{
    if (entityRenderList.size()>1) {
        //Any NULL values are brought to the top to be stripped off.

        bool passMade=false;
        Entity* temp;
        int n=entityRenderList.size()-1;
        for(int i=0; i<n; i++)
        {
            passMade=false;
            for(int j=0; j<n-1; j++)
            {
                if(depthSortFunction(entityRenderList[j],entityRenderList[j+1])) 
                {
                    //then swap them
                    temp = entityRenderList[j+1];
                    entityRenderList[j+1] = entityRenderList[j];
                    entityRenderList[j] = temp;
                    //and then notify the entities of the change
                    if (entityRenderList[j]!=NULL)   {entityRenderList[j]->renderListID=j;}
                    if (entityRenderList[j+1]!=NULL) {entityRenderList[j+1]->renderListID=j+1;}

                    passMade=true;
                    //std::cout<<"Swapping entries "<<j<<" and "<<j+1<<"...\n";
                }
            }
            if (!passMade) {
                break; //then it is sorted, as we have not needed to modify the array.
            }
        }
    }
    //Now, we strip off any NULL values from the top.
    while (!entityRenderList.empty() && entityRenderList.back()==NULL) {
        entityRenderList.pop_back(); //strip off last one
    }
}

应该发生的是在每次运行算法时从 vector 中删除所有 NULL 指针。然而，情况并非如此，任何 NULL 指针都停留在它们所在的位置，并且看起来根本没有排序。

注意:passMade bool 值在那里，因此如果进行了数组传递但未进行交换，算法将停止。

如有任何帮助，我们将不胜感激。提前致谢。

编辑:排序算法代码从 here 稍作修改.

Answer 1

j 循环限制中存在错误。例如，如果列表有 10 个元素，则 n 为 9，n-1 为 8，j 的最大值为 7。该循环可以交换 10 元素列表中的元素 7 和 8。它不能交换最后一对元素 8 和 9。

正如评论所建议的那样，使用已经过测试和工作的库排序会更好更简单。与其在进行过程中调整 renderListID 字段，不如在最后通过列表一次完成所有这些操作。如果在弹出 NULL 元素后执行此操作，则无需在该循环中测试 NULL。

    for(int i=0; i<entityRenderList.size(); i++)
    {
        entityRenderList[i]->renderListID=i;
    }