algorithm - 关于插入排序的代码

Question

我目前正在阅读 Cormen 等人的《算法导论》。我在推导它的伪代码时遇到了一些麻烦。我理解该算法的作用是直观的，以及某些元素是如何在整数数组中排序的。例如array = [5][2][4][6][1][3]，key为j=2，i = j-1。然后检查 i > 0 和 [5] 然后将 [2] 与 [5] 交换。令人困惑的部分来了:i = i -1??我的意思是我们刚刚设置了 i = j-1，为什么我们要再次减少 i？

伪代码如下:

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
          A[i + 1] = A[i]
          i = i - 1         //this the part I do not understand.
    A[i + 1] = key

Answer 1

此处概述的插入执行以下操作:

在每个 j 处，索引 j 之前的数组部分已排序，索引 j 之后未排序。

因此插入排序为新的 A[j] 找到一个合适的位置并将其插入。

例如，在j = 4和i = 3如果数组是

2 4 5 3 1 0  
      ^

The array before element 3 is sorted.  
1. So it checks that 3 is less than 5, hence copies 5 to array[i+1] (i+1 = 4).  
   2 4 5 5 1 0  
2. Then it decrements i checks that 3 is less than 4, hence copies 4 to array[i+1] (i+1 = 3).  
   2 4 4 5 1 0   
3. Then it checks that 3 is more than 2, hence stops and makes A[i+1] = key.  
   2 3 4 5 1 0