Geek
2021才发现的最简单的排序算法
排序算法是现代数据科学的基础。学习过数据结构或从事过商业编程的朋友，对各类排序算法都不陌生。但是，很少有人想到，这个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。未翻译，但看图就懂了。