c++ - 为什么当我删除 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] 这是错误的。为什么会这样？

标签： c++insertion-sort

Answer 1

当您这样做int key = arr[i];时，键的值将保存在变量中key。

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

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

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