0

第 1 部分
我知道 QuickSort 可以“就地”使用，但有人可以向我解释插入排序算法如何使用“就地”来做到这一点。

据我了解：

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

所以你会说这是“就地”，因为我们没有创建一个新数组来执行此操作，而只是比较数组中的两个元素？

如果我的理解是错误的，有人可以解释一下插入排序的算法。

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

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

4

1 回答 1

0

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

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 个交换。

冒泡排序确实到位，因为所有排序都发生在原始数组本身内，并且不需要单独的外部数组。

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

伪代码如下（万岁维基百科）：

 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

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

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

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

于 2015-04-20T11:00:09.770 回答