伪代码

for i = 1 to n-1:
   key = array[i]
   j = i-1
   while j >= 0 and array[j] > key:
      array[j+1] = array[j]
      j = j-1
   array[j+1] = key

现在，让我们把这段伪代码和我们的故事联系起来：

• i 是手中的卡片（或元素）：
  • i 表示我们当前正在查看的卡片（或元素）。
• key 是选中的卡片（或元素）：
  • key 是我们当前正在排序，并试图为它找到合适位置的卡片（或元素）。
• j 是手中已排序的卡片（或元素）：
  • j 表示我们在已排序的卡片（或元素）中查找的位置，以便为 key 找到合适的位置。
• array 是整副牌（或数组）：
  • array 是我们要排序的一副牌（或元素数组）。
• 移动和插入：
  • array[j+1] = array[j] 就像把卡片向右移动，为 key 腾出空间。
  • array[j+1] = key 是把 key 放到已排序卡片中的正确位置。

Insertion Sort is like sorting your cards – taking one at a time, finding its place among the already sorted ones. Simple, isn't it? In the next lesson, we'll see how to turn this understanding into code.