如何理解插入排序中改变键值？

Question

我知道什么是插入排序，但我看不懂代码。我搜索了所有关于排序的解释，而不是代码。如果您通过示例逐步回答问题，对我来说会更容易！谢谢！例如使用此代码。我将我的问题放在评论中以使其更清楚。

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
 /* if arr[j] > key, at here arr[j+1] has the number in arr[j] which is i
  * or key right? But now only arr[j+1] changed. There are only two same
  * numbers which is the bigger number, arr[j] is not changed to the smaller
  * number which arr[j+1] was.
  */
           j = j-1;
       }
       arr[j+1] = key;    
 /* so at here arr[j+1] now has the value of key which is arr[i], so the 
  * sorted arr[j+1] ended up unchanged? I know this step is supposed to 
  * change key to use it to compare numbers after.
  */
   }
}

Answer 1

你所说的key是一个临时变量，存储第i个元素的值我正在上传一张图片，可能会帮助你更好地理解它

考虑一个数组 A[]={7,4,5,2}

看到你已经用 1 初始化了变量 i 所以 key = arr[i]=arr1=4 in other words key is now 4.And also j=i-1 which will be 0. So moving on to the next statement while(j>=0 &&arr[j]>key) this checks if j is positive firstly and then checks if the value stored at jth position in the array(in this case is arr[0]=7) is greater than the key value then the loop initiates and now inside the loop body arr[j+1]=arr[j] in this statement the element of arr[j+1] which is arr1 被赋予了 arr[0] 的值 7。在这之后移动到下一个语句 j 是然后减 1，所以 j 现在是 -1。由于第一个条件现在为假，因此 while 循环将中断。现在退出循环，我们看到 arr [j+1] 现在将 arr[0] 分配给 "key" 值，即 4。类似地，每次如果有一个条件，其中前一个元素的值（其位置由 i) 确定大于它被交换的数组中当前元素（其位置由 j 确定）的值。如果循环的条件 (arr[j] > key) 不满足，语句 arr[j+1]=key 将毫无意义，因为 j+1 将等于 i。而且数值不会改变。

Answer 2

你的问题有点不清楚，所以让我试着解释一下代码中发生了什么，然后再尝试回答它们

外层循环变量i，表示数组中未排序数据的开始。它将通过 for loop

1

n

key 表示未排序区域的第一个元素，我们试图在 while loop 完成后将其放在正确的位置
j 表示排序区域中的最后一个索引。通过while loop

基本思想是在未排序的部分插入下一个元素，通过将所需元素从已排序的部分右移到这个新元素的最终位置

现在回答你的问题

if arr[j] > key, at here arr[j+1] has the number in arr[j]

是

which is i or key right?

没有。 arr[j+1] == key，仅在 while 的第一次迭代期间，而不是之后

But now only arr[j+1] changed.

是和否。在循环的一次迭代中，只有 arr[j+1] 发生了变化，但在下一次迭代 j = j -1 时，前一个元素发生了变化，或者说 is shifted right

There are only two same numbers which is the bigger number, arr[j] is not changed to the smaller number which arr[j+1] was.

在给定的迭代中 arr[j] 不会改变，但这并不意味着 arr[j] 在下一次迭代中不会改变。例如，假设 j = 10 是当前迭代。所以 a[10] 在 while 循环的这次迭代中不会改变，但它可能会在 j = 9 和 a[10] = a[9]

的下一次迭代中改变

so at here arr[j+1] now has the value of key which is arr[i]

不，arr[i] 可能会被 while 循环的第一次迭代覆盖，因此在 key

中备份

so the sorted arr[j+1] ended up unchanged? I know this step is supposed to change key to use it to compare numbers after.

根据上面的回答，这是无效的

如何理解插入排序中改变键值？

How to understand changing key value in insertion sort?

c

sorting

algorithm

insertion-sort

insertion