C++插入排序混淆

Question

我试图在C++中自己实现插入排序。我知道有很多例子，我把我的解决方案和现有的解决方案进行了比较，也不明白为什么我的解决方案不起作用。我知道有这样的库，但我想自己实现它。我有两个不同的实现，如下所示(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变量！

Answer 2

我将使用i=1来说明为什么它的工作方式与您预期的不同。

int j = i - 1;

J变成0。

myArr[j + 1] = myArr[j];

这里，myArr1被赋值为myArr。这就是问题所在，因为

myArr[j + 1] = myArr[i];

将myArr0的值赋给myArr1。

简而言之，移动删除了要插入的值。这就是为什么您需要将其复制到另一个变量(代码A中的键)。