这个奇怪的排序算法是什么？

Question

一些答案最初有这种排序算法：

\n

for i from 0 to n-1:\n    for j from 0 to n-1:\n        if A[j] > A[i]:\n            swap A[i] and A[j]\n

\n

请注意， 和i都j在整个范围内，因此j可以比 更大和更小i，因此它可以使对的顺序正确和错误（实际上它确实两者都做！）。我认为这是一个错误（作者后来这样称呼它），这会使数组变得混乱，但它似乎排序正确。但原因尚不清楚。但代码简单（全方位，并且没有+1像冒泡排序那样）使它变得有趣。

\n

这是对的吗？如果是这样，为什么它有效？它有名字吗？

\n

Python 实现与测试：

\n

from random import shuffle\n\nfor _ in range(3):\n    n = 20\n    A = list(range(n))\n    shuffle(A)\n    print(\'before:\', A)\n\n    for i in range(n):\n        for j in range(n):\n            if A[j] > A[i]:\n                A[i], A[j] = A[j], A[i]\n\n    print(\'after: \', A, \'\\n\')\n

\n

示例输出（在线尝试！）：

\n

before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]\nafter:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] \n\nbefore: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]\nafter:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] \n\nbefore: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]\nafter:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] \n

\n

编辑：有人指出了一篇关于该算法的非常好的全新论文。只是澄清一下：我们没有关系，这是巧合。据我所知，它是在引发我的问题的答案之前提交给 arXiv 的，并在我的问题之后由 arXiv发布的。

\n\n

Answer 1

这是一种正确但奇怪且低效的插入排序。

让我们首先通过A在每次完整的内循环迭代后打印来可视化它。例子：

before: [1, 12, 13, 8, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [19, 1, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 19, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 12, 19, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 19, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 19, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 19, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 16, 18, 19, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 15, 16, 18, 19, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 2, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 5, 4, 0, 10, 17]
        [1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 4, 0, 10, 17]
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 0, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

以图形方式显示，但每次交换后都会更新，红色条显示索引i（此处为代码）：

对于i = 0，它实际上或多或少地使列表混乱，但它带来了最大值A[0]（或一个最大值，如果有多个）。从那时起，这个值将充当哨兵。

由于这种初始混乱，很难（而且毫无意义）根据数组的初始状态来陈述不变量。相反，我们将其定义A0为外循环 for 之后数组的状态i = 0：

不变式：在某些外循环之后i：

• 总体最大值为A[i]
• A[0 to i]A0[0 to i]按排序顺序包含。

归纳证明：

基本情况i = 0很简单。

案例i > 0：在使用 this 进行外层循环之前i，我们有哨兵（总体最大值）在 处A[i-1]，并且A[0 to i-1]包含A0[0 to i-1]按排序顺序。现在，内部循环遍历所有元素，并且每当 时我们都会交换A[i]和。让我们再次看一下上面的示例行：A[j]A[j] > A[i]

[1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

是19哨兵，它之前的部分已排序，并且i是 11 的索引。当我们j从 0 到末尾时会发生什么？值 1、7 和 8 不大于 11，因此什么也不会发生。12更大，因此将与 11 交换：

[1, 7, 8, 11, 13, 15, 16, 18, 19, 12, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

现在索引处是 12 i。接下来它与 13 进行比较。由于 13 更大，因此它们被交换：

[1, 7, 8, 11, 12, 15, 16, 18, 19, 13, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

这样继续下去，总是交换，直到我们与哨兵交换：

[1, 7, 8, 11, 12, 13, 16, 18, 19, 15, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 18, 19, 16, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 19, 18, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

至此，11插入已排序部分就完成了。哨兵移动到索引i，然后它阻止内部循环期间的任何进一步交换（即与更右边的元素交换）。一般来说，对于一个新值（如 11），小于它的数字保留在原来的位置，大于它的数字被换出并放回右侧的一个位置。

当我们全部完成后，我们就完成了外循环i = n-1。然后不变量告诉我们A[0 to n-1]包含A0[0 to n-1]按排序顺序。即，数组确实最终正确排序。

为什么我称它为插入排序：在混乱之后i = 0，如果您在每个完整的内部循环之后查看数组，它与插入排序没有什么区别（请参阅顶部的大可视化块）。例如，11 只是被插入到其左侧的已排序部分中。只是插入发生的方式有所不同。普通插入排序将 11 向左“冒泡”直到其正确的位置，甚至不考虑更小的数字。相反，这里的算法从最左边开始搜索插入点，然后在那里插入 11 并将较大的数字“冒泡”到向右的哨兵。然后继续与现在坐在的哨兵进行无结果的进一步比较A[i]。

更新：smusamashah 分享了他们出色的可视化工具，它很好地让我们将该算法与声称的其他算法进行比较。单击冒泡排序、插入排序和选择排序右侧的复选标记，然后单击开始。您将再次看到我们的排序非常类似于插入排序，并且与其他排序完全不同。如果您改为进行交换排序（遗憾的是不包括在内），您会发现这更像是选择排序（但速度较慢，因为它交换更多并且该工具显示所有交换）。

Answer 2

为了证明它是正确的，你必须找到某种不变量。在循环的每次传递中都是如此。

看看它，在内循环的第一遍之后，列表的最大元素实际上将位于第一个位置。

现在，在内循环的第二遍中，i = 1，第一个比较是在i = 1和之间j = 0。所以，最大的元素在位置0，经过这次比较，它将被交换到位置1。

一般来说，不难看出，在外循环的每一步之后，最大的元素都会向右移动一位。因此，在完成完整步骤之后，我们至少知道最大的元素将位于正确的位置。

其余的呢？假设第二大元素位于i当前循环的位置。我们知道最大的i-1元素位于前面讨论的位置。计数器j从 0 开始。所以现在我们正在寻找第一个，A[j]它是A[j] > A[i]。嗯，A[i]是第二大元素，所以第一次发生这种情况是j = i-1在第一个最大元素处的时候。因此，它们是相邻的并被交换，现在处于“正确”的顺序。现在A[i]再次指向最大的元素，因此对于内部循环的其余部分，不再执行交换。

所以我们可以说：一旦外循环索引移过第二大元素的位置，第二大元素和第一大元素将按正确的顺序排列。现在，在外循环的每次迭代中，它们将一起向上滑动，因此我们知道在算法结束时，第一个和第二大元素都将位于正确的位置。

那么第三大元素呢？好吧，我们可以再次使用相同的逻辑：一旦外循环计数器i位于第三大元素的位置，它将被交换，使其位于第二大元素的正下方（如果我们发现了一个）已经！）或者就在第一个最大元素下方。

啊。现在我们有了不变量：k在外循环迭代之后，以位置 结束的 k 长度元素序列k-1将按排序顺序排列：

第一次迭代后，位置 0 处的 1 长度序列将处于正确的顺序。那是微不足道的。

在第二次迭代之后，我们知道最大的元素位于位置 1，因此显然序列A[0],的顺序A[1]是正确的。

现在假设我们处于步骤k，因此直到位置的所有元素都k-1将按顺序排列。现在i = k我们迭代一下j。其作用基本上是找到新元素需要插入到现有排序序列中的位置，以便正确排序。一旦发生这种情况，其余元素就会“冒泡”，直到现在最大的元素位于该位置i = k并且不会发生进一步的交换。

因此，最终在步骤 结束时N，直到位置的所有元素都N-1处于正确的顺序，QED。

Answer 3

我不太确定上述算法是否有明确的名称，但从一些快速输出分析来看，它看起来像是插入排序的低效实现，其中排序区域在运行迭代后从索引0到包含区域。ii

打印调试

如果我们在内循环后面放置一条 print 语句，则可以通过检查来验证这一点：

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]
    print(A) <- add here

A = [5, 5, 0, 9, 2]
0.  [9, 5, 0, 5, 2]
1.  [5, 9, 0, 5, 2]
2.  [0, 5, 9, 5, 2]
3.  [0, 5, 5, 9, 2]
4.  [0, 2, 5, 5, 9]

证明

我们可以通过i外循环 的归纳来证明这一点。运行迭代 后，包含或 的i索引将被排序。0 to iAA[0:i]A[i] = max(A)

基本情况：i = 0

对于i = 0， 的最大值A将存储在索引处0。这几乎是通过检查算法得出的。

归纳步骤：i > 0

我们的归纳假设是 已A[0:i-1]排序 且A[i - 1] = max(A)。迭代中会发生什么i？基本上，我们正在确定A[i]应放置在排序区域中的位置（由内部循环处理），然后重新调整它。

子情况 1：A[i] < A[j]对于某些0 <= j <= i - 1

从上面的算法来看，A[j]将被交换为Ap = A[i]。请注意，根据我们的假设，A[0:i-1]已排序。因此，对于其余的索引，j + 1 <= i我们将在插入后重新排序已排序的区域Ap。由此可见，A[0:i]将在 时进行排序j = i。

子情况 2：A[i] >= A[j]对于所有人0 <= j <= i - 1

在这种情况下不会发生交换，并且A[0:i]从A[0:i-1]正在排序和 的事实来看， 已排序A[i] >= A[i - 1]。

其他情况：j > i

请注意，j到达索引后i， 的最大值A将回到索引处i。因此，对于内循环的其余部分，不会进行任何交换。因此，接下来A[0:i]将进行排序。

因为上述情况适用于所有情况i < n = len(A)，所以我们可以得出结论，运行迭代n - 1将有效排序A[0:n-1] = A。

验证/改进

从上面的证明我们看到，对于的检查j > i是多余的。为了使算法更加高效并且与通常的插入排序更加协调，我们可以运行下面的代码来对数组进行排序。

for i from 0 to n-1:
    for j from 0 to i: <- claim this line can be changed
        if A[j] > A[i]:
            swap A[i] and A[j]