算法简介中的插入排序

Question

在算法第2版简介中，我找到了插入排序伪代码

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do A[i+1] <- A[i]
7              i <- i -1
8          A[i + 1] <- key

但我无法理解交换如何在这里工作。

我认为它需要像这样的交换操作

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do temp <- A[i+1]
7              A[i+1] <- A[i]
8              A[i] <- temp
9              i <- i -1
10         A[i + 1] <- key

我弄错了什么？请帮忙

Answer 1

插入排序中发生的事情不是交换。

它将每个项目移动大于您想要插入的项目，从当前已排序部分的末尾向下处理一个索引，然后在旧值向上移动后将新记录插入正确的位置。

Answer 2

但我无法理解交换如何在这里工作。

不，不是的。

该值已在开头保存。

它保存j，然后移动所有其他元素，直到找到合适的位置

Answer 3

我遇到了同样的问题。下面是C中的代码，它正确地实现了上面的伪代码。

关于这一点的棘手部分是伪代码使用基于1的数组符号，这与大多数编程语言不同！

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }

Answer 4

代码正在进行“多次交换”，更准确地说是将k个元素按原位旋转一个位置。这需要一个辅助key变量，就像交换一样。