插入排序算法就地和循环变体

Question

第 1 部分
我知道可以使用 QuickSort 'in place' 但有人可以向我解释插入排序算法如何使用 'in place'.

据我了解：

插入排序从第一个值开始并将其与下一个值进行比较，如果该值小于我们的值，则它们交换位置。我们递归地继续这个。（简短说明）

所以你会说这是 'in place' 因为我们没有创建一个新数组来做这件事，而只是比较数组中的两个元素？

如果我的理解有误，谁能解释一下插入排序算法就位。

第 2 部分
另外，我将如何使用插入排序来说明循环不变量的概念？

我知道循环不变量是在循环的每次迭代之前和之后立即为真的条件，但我不确定这与插入排序有何关系。

Answer 1

就像评论部分提到的 Thorsten 一样，您已经描述了冒泡排序。修改自Wikipedia，冒泡排序的伪代码如下：

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   for i = 1 to n inclusive do // Outer Loop
     for j = 1 to n-1-i inclusive do
       /* if this pair is out of order */
       if A[j] > A[j+1] then
         swap(A[j], A[j+1])
       end if
     end for
   end for
end procedure

冒泡排序（对于外循环）中的循环不变量是，在循环的每次迭代之后，整个数组直到 i 的当前值将被排序。这是因为，每次到达外层循环时，都会在经过内层循环的所有迭代（从 i 到 n-1）之后，找到那里的最小元素并将该元素与第 i 个元素交换。

冒泡排序确实就位，因为所有排序都在原始数组本身内进行，不需要单独的外部数组。

编辑-现在进入插入排序：

伪代码如下（万岁Wikipedia）：

 for i = 1 to length(A) - 1
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x[3]
 end for

在这里，在每个步骤中，对于每个元素，您 select 将其插入到数组中的适当位置，即，您将它插入到第一个较小的元素之后比它在数组中。更详细一点，内部循环所做的是，它不断向右移动元素，直到遇到比所考虑的元素更小的元素，此时您将元素插入到较小的元素之后。这意味着对上述元素之前的每个元素进行排序。外层循环确保对数组中的所有元素完成此操作，这意味着在外层循环完成时，数组已排序。

外层循环的循环不变量与之前一样，在第 i 次迭代后，所有元素直到当前 i 将被排序。然而，就在第 i 次交互之前，将对 i-1 之前的所有元素进行排序。

插入排序算法不需要外部数组进行排序。更具体地说，所有操作都是在数组本身上完成的（除了我们需要存储我们当前试图插入其适当位置的元素的一个变量），并且没有使用外部数组 - 没有从这个数组复制例如，另一个。因此，算法所需的 space 复杂度（当然不包括 space 数组本身占用的）将是 O(1)，而不是依赖于数组的大小，并且就地排序，很像冒泡排序。

插入排序算法就地和循环变体

Insertion Sort Algorithm In place and loop variant

quicksort

insertion-sort

loop-invariant