这种特殊排序算法是什么？其正确性、运行原理及命名问询

算法正确性结论 #

该算法完全具备排序正确性，任意乱序数组经过该算法处理后都可以得到升序排列的结果，多轮随机测试也验证了这一点。

正确性证明 #

我们可以通过反证法简单验证：
假设算法运行结束后存在逆序对：即存在位置p < q，但A[p] > A[q]。我们回溯运行过程：当外层循环i = q时，内层循环会遍历到j = p，此时A[p] > A[q]满足交换条件，两个元素会被交换，交换后A[q]为更大值，A[p]为更小值。后续外层循环处理i > q的位置时，即使触发交换也只会将更大的值换到更靠后的i位置，不会再破坏p < q位置的升序关系，因此最终不可能存在逆序对，算法必然正确。

运行原理 #

该算法的核心逻辑可以这么理解：

• 外层循环逐个遍历数组的每个位置i，内层循环无差别遍历整个数组的所有位置j
• 只要发现j位置的元素比当前i位置的元素大，就将两个元素交换，保证每一步i位置存放的都是当前已经遍历过的j位置中最大的元素
• 虽然内层循环会修改i之前已经处理过的位置的元素，但经过两轮完整的全数组遍历后，所有逆序对都会被逐步修正，最终整个数组变为升序
  该算法的时间复杂度为固定的O(n²)，不管输入数组是否有序，都需要执行n²次比较，最多O(n²)次交换，效率低于插入排序、冒泡排序等同复杂度的常用排序算法。

官方命名 #

该算法因为逻辑反常识、代码极简，2021年才有专门的学术论文对它进行整理研究，论文中将它命名为 「极简排序（The Simplest Sorting Algorithm）」，开发者社区也常根据它的特性称它为「傻排序」「惊喜排序」，目前没有更通用的标准命名。 #

相关代码参考 #

算法伪代码

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]

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')

内容的提问来源于stack exchange，提问作者no comment