这个奇数排序算法是什么？

Question

有些答案最初有这样的排序算法：

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]

请注意，i和j都是全范围的，因此j可以比i大，也可以比i小，所以它可以使成对的顺序正确，也可以使成对的顺序错误（实际上这两种顺序都正确！）。我认为这是一个错误（作者后来称之为错误），这会混淆数组，但它看起来排序正确。不过，原因并不明显。但是代码的简单性（范围很广，没有像冒泡排序那样的+1)使它变得有趣。

正确吗？如果是这样，它为什么起作用？它有名字吗？

带测试的Python实现：

from random import shuffle

for _ in range(3):
    n = 20
    A = list(range(n))
    shuffle(A)
    print('before:', A)

    for i in range(n):
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]

    print('after: ', A, '\n')

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

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

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

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

Answer 1

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

看一下，在第一次传递内部循环之后，列表中最大的元素实际上将位于第一个位置。

现在，在内循环的第二遍中，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]再次指向最大的元素，因此对于内部循环的其余部分不再执行交换。

所以我们可以说：一旦外部循环索引移动过第二大元素的位置，第二大元素和第一大元素将按正确的顺序排列。在外循环的每一次迭代中，它们会一起滑动，所以我们知道在algo的末尾，第一大元素和第二大元素都会在正确的位置。

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

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

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

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

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

因此，在步骤n的最后，所有元素直到位置n-1的顺序都是正确的，QED。