为什么我的 Insertion 一开始冒泡了一个更高的值？

Question

我使用插入排序对由“+”分隔的数字组成的字符串进行排序。数字只能是 1、2 或 3。虽然我认为代码可以完美运行，但它给了我一些奇怪的输出。

    #include <iostream>
    #include <string>
     
    typedef long long ll;
     
    using namespace std;
     
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
     
        string s;
        cin >> s;
     
        for (int i = 2; i < s.size(); i += 2)
        {
            int value = s[i];
            int key = i;
            while (key > 0 && s[i-2] > value)
            {
                s[key] = s[key-2];
                key = key - 2;
            }
            s[key] = value;
        }
     
        cout << s;
    }

当我输入

2+1+2+2+2+3+1+3+1+2

输出很奇怪

2+1+1+1+2+2+2+2+3+3

最后的 2 被带到开头。

如果我从输入中删除最后 2 个，结果如预期的那样

2+1+2+2+2+3+1+3+1

1+1+1+2+2+2+2+3+3

我花了很多时间调试，却找不到问题所在。

Answer 1

while (key > 0 && s[i-2] > value)
您在代码中使用了 s[i-2] 而不是 s[key-2]，这意味着如果 value 小于 ，则您的数字一直向左移动 s[i-2] 而不是一旦左边的数字是 <= 就停止。
TL;DR 将 s[i-2] 更改为 s[key-2] 就可以了。

为什么我的 Insertion 一开始冒泡了一个更高的值？

Why is my Insertion bubbling a higher value to the start?

c++

c++17