2021才发现的最简单的排序算法

majer @ 2023.11.02 , 04:56 下午

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

[ 广告 ]
赞一个 (12)

PREV :
NEXT :

nut 2023年11月02日 17:37 / 广东省珠海市1楼
不是很明白，不就是一个更加啰嗦的冒泡吗？
#11797972 / 举报 / OO [46] / XX [11]
蓝波万 2023年11月02日 17:45 / 广东省广州市2楼
这也能发文章？算法优点：代码最少。
#11797996 / 举报 / OO [7] / XX [13]
蓝波万 2023年11月02日 17:45 / 广东省广州市3楼
这也能发文章？算法优点：代码最少。
#11797997 / 举报 / OO [13] / XX [3]
XX侠 2023年11月02日 18:00 / 广东省广州市4楼
既然不用管效率只管代码量，这样行不行？
for i = 1 to n-1 do
如果 A[i] > A[i+1] 那么
交换 A[i] 和 A[i+1]
i =1
#11798019 / 举报 / OO [2] / XX [6]
nut 2023年11月02日 18:06 / 广东省珠海市5楼
好吧，我错了。第n（n>2）个循坏后的结果可以看出前n个数是原数组前n个数的插入排序。
[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厉害多了，帮我补齐的代码的逻辑符号是正确的！
#11798028 / 举报 / OO [7] / XX [2]
Blastom 2023年11月02日 18:47 / 重庆市6楼
和冒泡不同，这个流程不是 1换2，2换3这种相邻替换。
所以可靠性很难证明。
#11798086 / 举报 / OO [3] / XX [5]
Blastom 2023年11月02日 18:52 / 重庆市7楼
完全不对，就是每一次迭代额外检查了前面已经排好的冒泡。
#11798098 / 举报 / OO [3] / XX [4]
潜伏者 2023年11月02日 18:56 / 山东省8楼
我感觉我非常喜欢这个算法，因为偶尔编程要用到，但搞不懂各种排序理论
#11798104 / 举报 / OO [0] / XX [10]
celk 2023年11月02日 20:07 / 广东省广州市9楼
@nut
这东西完全不是冒泡……
冒泡的核心是在内层 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 位已经是最小的，不用再比较了。
#11798219 / 举报 / OO [12] / XX [0]
蛋友e5e64bc595b8c 2023年11月02日 20:50 / 法国10楼
感觉这个的优点是可以很方便用机械实现，比起冒泡排序少一个i+1的逻辑，所以可以用一对齿轮，小齿轮转一圈大齿轮转1格，就能完成取元素操作，然后比较上也没有相等条件，可以使用一个简单的机械开关完成元素置换

#11798247 / 举报 / OO [18] / XX [0]
celk 2023年11月02日 22:36 / 广东省广州市11楼
这东西完全不是冒泡……
冒泡的核心是在内层 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 的。
#11798389 / 举报 / OO [6] / XX [0]
帽子 2023年11月02日 22:57 / 上海市徐汇区12楼
原来2021年ICPC南京的D题出自这里：https://codeforces.com/gym/103470/problem/D
#11798415 / 举报 / OO [9] / XX [0]
蛋友24cdc70b6fd8 2023年11月03日 15:09 / 江苏省无锡市13楼
一开始我也以为就是冒泡，只是循环次数多了些。
直到我把冒泡算法第二个循环改掉（但是没有改if条件）之后，发现，出来的排序结果是和冒泡颠倒的。
我才知道他不是冒泡。
理解了为什么顺序颠倒了，就理解为什么他不是冒泡了。
#11799727 / 举报 / OO [4] / XX [0]
酷酷的就 2023年11月03日 16:57 / 新疆乌鲁木齐市14楼
for i = 1 to n:
new thread(i)->{print (i);}
这个不是更简单?
#11799983 / 举报 / OO [0] / XX [4]