C++插入排序困惑

Question

我正在尝试用 C++ 自行实现插入排序。我知道有很多示例，我将我的解决方案与现有解决方案进行了比较，但不明白为什么我的解决方案不起作用。我知道有用于此的库，但我想自己实现它。我有 2 种不同的实现，如下所示(A - 一种有效，B - 一种无效)。

这是 A - 确实有效。这里没有新内容。

    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 下标而不是键:

    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 是不正确的。任何指导将不胜感激。

Answer 1

这是一个很好的手工浏览代码的练习。有什么变化？ 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 变量!