算法导论中的插入排序

Question

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

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

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

Answer 4

我遇到同样的问题。下面是正确实现上述伪代码的 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");
 }