今天看到一个新发现的有趣的排序算法。

[olist]

新算法：
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]

等价的冒泡排序算法：
for i = 1 to n do
for j = i + 1 to n do
if A[i] > A[j] then
swap A[i] and A[j]

算法来源： https://arxiv.org/pdf/2110.01111.pdf

第二个算法不是冒泡排序，也不是其它常见排序算法的标准写法。

这个算法简单且好记，判断条件是小于号时是升序排序，大于号时是降序排序。但算法的正确性却不显而易见。

[Kilerd]

思绪良久，新算法这个不是最弱鸡的排序方法吗？

[rrfeng]

？？？

[iBugOne]

就是插入排序，但是多做了一倍的无用功

[Mohanson]

建议楼上 3 楼仔细看代码, 这算法很反直觉啊

[zzxxisme]

1. 这个论文里面提到这个 新算法 的好处不是在于效率，而是在于它的简单性，以及它的 看上去不是那么正确 的特点，然后这个论文去证明它的正确性。这个算法的确最后把 A 数组进行了升序排序。
2. 你说的第二个算法不是传统认为的冒泡… 冒泡每次 swap 的是相邻的两个数，而你的第二个算法是为`A[i]`找`A[i .. n]`的最小值。

[wangyu17455]

这不就是没有优化过的冒泡排序

[olist]

@iBugOne 哈哈，确实就是个低配版的插入排序。

[olist]

@zzxxisme 你说出了我分享这个算法的原因:-)

[iAIR]

我想叫熊瞎子掰苞米排序……见到更好的就把手上的扔地上

[Blanke]

简单选择排序

[abysmalIQ]

这个比其他排序好记在哪？

[chendy]

感觉像选择排序
选择排序是记住下标最后换，这个是不记下标一直换

[Junzhou]

即使易于记忆，但是没什么实用性。面试快排，写业务调封装。

[9c04C5dO01Sw5DNL]

第二个是选择排序，每轮选择最小的排在左侧，跟标准写法比 swap 次数多了。

第一个是循环次数比第二个要多的选择排序，不过是降序。。。。

[olist]

@giiiiiithub 第一个也是升序，是不是反直觉？

[9c04C5dO01Sw5DNL]

@olist 擦，还真是，第一个不是选择排序。。。。。确实是一种没见过的排序方法

[njutree]

这种思路感觉计算机发展这么多年早就有大佬想过了，证明正确性也不是很难。关键是这个思路没有暖用交换次数多效率极低，如果仅仅是为了简单：

for i = 1 to n do
for j = 1 to n do
if A[i] > A[j] then
swap A[i] and A[j]

这样写其实也是一样的

[krapnik]

https://www.ithome.com/0/579/187.htm

[xianzhe]

我见过最骚的排序是睡觉排序。列表中每个元素都开新线程，然后睡上元素值大小的时间，到点输出。

[vone]

还是 Bogo 排序更巧妙一点。

https://zh.wikipedia.org/wiki/Bogo%E6%8E%92%E5%BA%8F
https://z3.ax1x.com/2021/10/11/5ZwCg1.png

Bogo 排序（ bogo-sort ）是个非常低效率的排序算法，通常用在教学或测试。其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自 Quantum bogodynamics，又称 bozo sort 、blort sort 或猴子排序（参见无限猴子定理）。
伪代码：

function bogosort(arr)
while arr is not ordered
arr := 随机排列(arr)

其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。

[tfdetang]

@xianzhe 被这个惊到了，感觉是段子

[dafen7]

@tfdetang 这应该就是段子，老程序员面试段子了

[wzzb]

这应该是最“反直觉”的排序算法吧，没暖用是真的