排序算法是现代数据科学的基础。学习过数据结构或从事过商业编程的朋友，对各类排序算法都不陌生。但是，很少有人想到，这个2021年才发现的最简单(但远不是最高效)算法竟然可以完成排序。或许，从业经验越久，越会觉得不可思议。咋看会以为：“这不就是一个错误的冒泡排序么，只是第二行把范围写错，第三行交换的条件写反了罢了😁。”
执行下面的算法就能按递增顺序对大小为 n 的数组进行排序：
——————————————————————
for i=1 to n do
for j=1 to n do
如果 A[i] < A[j] 那么
交换 A[i] 和 A[j]
——————————————————————
经过整整 n² 次比较，执行交换数 ≤ C(n，2) + 1。
英国莱斯特大学的计算和数学科学学院的Stanley P. Y. Fung于2021年10月3日提交到了arXiv论文，题为Is this the simplest (and most surprising) sorting algorithm ever?(《这是有史以来最简单(也最令人惊讶)的排序算法吗？》。
这篇论文提出了一种极其简单的排序算法，它看起来似乎是错误的，但作者证明了它实际上是正确的。作者还将它与其他简单的排序算法进行了比较，并分析了它的一些奇特性质。
这个排序算法的核心思想是：对于一个有n个元素的数组A，用两层循环遍历所有的(i,j)对，如果A[i]小于A[j]，就交换它们。作者称之为 ICan’tBelieveItCanSort 算法。
作者指出，这个算法没有什么优点。它很慢——无论最坏情况、平均情况还是最好情况，它都需要Θ(n^2)时间。它不必要地比较了所有位置的数对，而且还重复了两次。它似乎没有什么直觉依据，而且它的正确性也不是完全显而易见的。作者认为，你肯定不想用它作为介绍排序算法的第一个例子。它不稳定，不适合外部排序，不能对在线的输入进行排序，也不能从部分排序的输入中受益。它唯一的吸引力可能是它的简单性，无论是代码行数还是两个循环的“对称性”。
作者表示，很难想象这个算法以前没有被发现过，但他们没有找到任何相关的参考文献。
下面简单的讲解视频来自算法博主Polylog。未翻译，但看图就懂了。
王摸鱼夏款T恤第二波发布，有粉色和无图速干款
for i = 1 to n-1 do
如果 A[i] > A[i+1] 那么
交换 A[i] 和 A[i+1]
i =1
[3, 7, 2, 4, 6, 5, 1]
[7, 3, 2, 4, 6, 5, 1]
[3, 7, 2, 4, 6, 5, 1]
[2, 3, 7, 4, 6, 5, 1]
[2, 3, 4, 7, 6, 5, 1]
[2, 3, 4, 6, 7, 5, 1]
[2, 3, 4, 5, 6, 7, 1]
[1, 2, 3, 4, 5, 6, 7]
#################
[3, 7, 2, 4, 6, 5, 1]
[1, 7, 3, 4, 6, 5, 2]
[1, 2, 7, 4, 6, 5, 3]
[1, 2, 3, 7, 6, 5, 4]
[1, 2, 3, 4, 7, 6, 5]
[1, 2, 3, 4, 5, 7, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
顺便提一嘴，chat-gpt厉害多了，帮我补齐的代码的逻辑符号是正确的！
所以可靠性很难证明。
这东西完全不是冒泡……
冒泡的核心是在内层 j 循环里确定出最大/最小的，放在固定的第 i 位置，而内层 j 循环不管怎么执行都是不影响的，也就是说，第 j 位元素无论怎么被摆到第 i 位之后又被扔回去都是不影响的，只要保证内层 j 循环的遍历性就可以了。
但是这个 ICan'tBelieveItCanSort 的可行性完全依赖于内层 j 循环的遍历顺序，它需要将第 j 位元素临时摆到第 i 位之后再放到另一个第 j 位上去，关键在于它后来被扔到了什么地方，这是它能排序的关键。
例如假如把内层 j 循环改成先 for j = 2 to n 再 j = 1，最后出来的就不是排序的，这就和冒泡不一样……
这是一种费工夫的插入排序，当前面 i-1 个元素排好序之后，考察第 i 个元素，由于 1 to i 的内层 j 循环遍历顺序，它会将第 i 个元素刚好插换到前面排好序的序列中，将比该元素小的第 j 位置先临时交换到第 i 位然后再交换回去第 j+1 位置。接下来的 i+1 to n 的内层循环就完全是多余的，因为此时的第 i 位已经是最小的，不用再比较了。
冒泡的核心是在内层 j 循环里确定出最大/最小的，放在固定的第 i 位置，而内层 j 循环不管怎么执行都是不影响的，也就是说，第 j 位元素无论怎么被摆到第 i 位之后又被扔回去都是不影响的，只要保证内层 j 循环的遍历性就可以了。
但是这个 ICan'tBelieveItCanSort 的可行性完全依赖于内层 j 循环的遍历顺序，它需要将第 j 位元素临时摆到第 i 位之后再放到另一个第 j 位上去，关键在于它后来被扔到了什么地方。
例如假如把内层 j 循环改成先 for j = 2 to n 再 j = 1，最后出来的就不是排好序的……
它其实是一种复杂化的插入排序，当前面 i-1 个元素排好序之后，考察第 i 个元素，由于 j = 1 to i 的内层循环遍历顺序，它会将第 i 个元素刚好插换到前面排好序的序列中，将比该元素小的第 j 位置先临时交换到第 i 位然后再交换回去第 j+1 位置。接下来的 j = i+1 to n 的内层循环就完全是多余的，因为此时的第 i 位已经是最小的，if 判断是不会 true 的。
直到我把冒泡算法第二个循环改掉（但是没有改if条件）之后，发现，出来的排序结果是和冒泡颠倒的。
我才知道他不是冒泡。
理解了为什么顺序颠倒了，就理解为什么他不是冒泡了。
new thread(i)->{print (i);}
这个不是更简单?