为什么删除 Key 变量时插入排序会崩溃

Question

最近，我学习了如何使用插入排序。所以，我开始修改它的代码。

#include<bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[] = {4,3,2,10,12,1,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    for(int i=1; i<n; i++)
    {
        int key = arr[i]; // line a
        int j = i-1;

        while(j>=0 && arr[j]>key) //line b
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; //line c
    }

    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

因为 key = arr[i]，我删除了“line a”并在“line b”和“line c”处放置了 arr[i] 而不是 key。我期待相同的结果，但输出是 [4 4 4 10 12 12 12 12] 这是错误的。为什么会这样？

Answer 1

当您执行int key = arr[i];时，键的值保存在变量key中。

当您执行 while(j>=0 && arr[j]>arr[i]) 时，您使用 arr[i] 的当前值。一开始是一样的，但是随着 while 循环的运行，你开始修改 arr:

arr[j+1] = arr[j];

当 j+1 等于 i 时，这将最终修改 arr[i]。因此，对于循环的进一步迭代，您将检查不同的值。

为什么删除 Key 变量时插入排序会崩溃

Why does insertion sort break down when I remove Key variable

c++

insertion-sort