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 的示例输出：

这是 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 的示例输出：

我不明白，我唯一改变的是没有将当前值存储在变量中。我知道我可以很容易地做到这一点，一切都会好起来的，但让我困扰的是我不知道为什么 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];

这里myArr[1]被赋值为myArr[0]。这就是问题所在，as

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

将 myArr[0] 的值（在前面提到的行中修改）分配给 myArr[1]。

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

C++插入排序混乱

C++ Insertion sort confusion

c++

algorithm

insertion-sort