算法导论中的插入排序

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

但是我不能理解swap是如何工作的。

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

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

，但我不能理解swap是如何工作的。

不不是的。

该值已保存在请求中。

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

Answer 3

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