c++ - C++插入排序困惑

我尝试自己在C++中实现插入排序。我知道有很多例子，我把我的解决方案和现有的解决方案进行了比较，不明白为什么我的工作不起作用。我知道有一些库可供使用，但我想自己实现它我有两个不同的实现，如下所示（一个有效，一个无效）。
这是一个有效的。这里没什么新鲜事。

    int myArr[5] = {5,4,3,2,1};

    for (int i = 1; i < 5; i++){

        int j = i - 1;
        int key = myArr[i];

        while(myArr[j] > key && j >= 0){
            myArr[j + 1] = myArr[j];
            j = j - 1;
        }
        myArr[j + 1] = key;

        //Printing array to see what changed:
        for (size_t k = 0; k < 5; ++k){
            cout << myArr[k] << " ";
        }
        cout << endl;
   }

A的样本输出：

    4 5 3 2 1
    3 4 5 2 1
    2 3 4 5 1
    1 2 3 4 5

这是B，我想到的东西B与A非常相似，除了我指出的行，我选择使用myarr下标而不是key：

    int myArr[5] = {5,4,3,2,1};

    for (int i = 1; i < 5; i++){

        int j = i - 1;
        //int key = myArr[i]; //DIFFERENT FROM **A**


        //************** DIFFERENT FROM A **************
        //I didn't use "key", instead I chose to use myArr[i]
        while(myArr[j] > myArr[i] && j >= 0){
            myArr[j + 1] = myArr[j];
            j = j - 1;
        }

        //************** DIFFERENT FROM A **************
        //Same here: I use myArr[i] instead of key
        myArr[j + 1] = myArr[i];

        //Printing array to see what changed:
        for (size_t k = 0; k < 5; ++k){
            cout << myArr[k] << " ";
        }
        cout << endl;
   }

B的样本输出：

    5 5 3 2 1
    5 5 5 2 1
    5 5 5 5 1
    5 5 5 5 5

我不明白，我唯一改变的是没有将当前值存储在变量中我知道我很容易做到，一切都会好起来的，但让我烦恼的是，我不知道为什么B是不正确的任何指导都将不胜感激。

最佳答案

这是手工遍历代码的一个很好的练习。有什么变化？key是值在myArr[i]时的临时存储看似无害的重构的问题在于myArr[j + 1]在内部循环的第一次迭代中是myArr[i]这一事实。告示

int j = i - 1;
...
myArr[j + 1] = myArr[j]; // j + 1 === i

基本上是：

myArr[i] = myArr[j]; // whoops!

在这里，我们将myArr[i]重新分配给其他对象，而不是在key中复制和存储值。每当myArr[i]元素还没有排序时，我们在每个外循环迭代中都会丢失一个元素。
保留key变量！

关于c++ - C++插入排序困惑，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56613677/