插入排序问题

Question

我正在为我的入门C++课进行插入排序，它似乎正在工作，但我的排序列表中不断重复。

在主

Storage s;
for (int i = 0; i < 20000; ++i)
{
    cout << "adding " << iss[i] << " to sorted list" << endl;
    s.Add(iss[i]);
}

和存储.cpp

    void Storage::Add(int num)
{
    it = mylist.begin();
    if (mylist.empty())
    {
        Node tem(num);
        mylist.push_front(tem);
    }
    else 
    {
        while (it != mylist.end())
        {
            if (num < (*it).GetNumber())
            {
                Node temp(num);
                mylist.insert(it, temp);
            }
            it++;
            if (it == mylist.end())
            {
                Node te(num);
                mylist.push_back(te);
            }
        }
    }
    it = mylist.begin();
    while (it != mylist.end())
    {
        cout << (*it).GetNumber() << ',';
        it++;
    }
    cout << endl << mylist.size() <<endl;
}

Node只存储要添加到列表中的数字以及时间，这是在Node内计算的。

我不知道为什么我会重复，提前感谢您的帮助。

Answer 1

看看你的while循环。

    while (it != mylist.end())  // Here
    {
        if (num < (*it).GetNumber()) // Here
        {
            Node temp(num);
            mylist.insert(it, temp); // and here
        }
        it++;
        if (it == mylist.end())
        {
            Node te(num);
            mylist.push_back(te); // And here
        }

你了解休息了吗？ 添加后，您会继续执行循环，并在最后添加它。

Answer 2

在 while 循环的第二个 if 条件下，您总是在列表的末尾添加一个导致重复的新节点。

Answer 3

我认为问题出在这个循环中

    while (it != mylist.end())
    {
        if (num < (*it).GetNumber())
        {
            Node temp(num);
            mylist.insert(it, temp);
        }
        it++;
        if (it == mylist.end())
        {
            Node te(num);
            mylist.push_back(te);
        }
    }

如果列表有一个元素，那么在它++之后，迭代器将等于end（），你将添加一个新元素。之后，当前迭代器端变为无效。我会按以下方式重写它

    while ( it != mylist.end() && !( num < (*it).GetNumber() ) ) it++;
    Node temp( num );
    if (it == mylist.end()) mylist.push_back(temp);
    else mylist.insert(it, temp);