专栏名称: 数盟
数盟(数据科学家联盟)隶属于北京数盟科技有限公司,数盟致力于成为培养与发现“数据科学家”的黄埔军校。 数盟服务包括:线下活动、大数据培训。 官网:http://dataunion.org,合作:[email protected]
目录
相关文章推荐
数据派THU  ·  从头构建GPT文本分类器(Python) ·  昨天  
数据派THU  ·  【ICLR2025】AdaWM:基于自适应世 ... ·  4 天前  
CDA数据分析师  ·  【干货】画用户画像与找相亲对象一样简单 ·  2 天前  
51好读  ›  专栏  ›  数盟

这些奇怪的排序算法,你没见过吧?

数盟  · 公众号  · 大数据  · 2017-08-07 22:00

正文

(点击 上方公众号 ,可快速关注)


编译: 伯乐在线 - 孙腾浩

如有好文章投稿,请点击 → 这里了解详情



【伯乐在线/算法爱好者 导读】:如果有人问你哪种排序算法最奇怪,可能你会先在冒泡排序、选择排序、快速排序等常见排序算法中「搜索」了。

有人在 Quora 上也发帖问了这个问题。于是乎,各种脑洞大开的奇特算法就被列出来了。它们可能存在性能问题或无法实现,但是不可否认其创造性。

睡眠排序(Nipun Ramakrishnan 的回答)

这个搞笑算法流传于 4chan 的 /prog/ 板块。无从查证具体出自哪位程序员,伪代码如下

procedure printNumber ( n )

sleep n seconds

print n

end

for arg in args

run printNumber ( arg ) in background

end

wait for all processes to finish


算法运行如下: 对于数组中每个元素 x,开启一个新程序:

  • 休眠 x 秒

  • 打印 x 所有元素同时开始计时。 只适用于非负数字。

Bogo 排序/猴子排序 (Ryan Turner的回答)

Bogo 排序/猴子排序,名字很奇怪。它是愚蠢排序中的一员。

主要来说,算法就是你把元素随机排列。

如果没有排好序,再次把元素随机排列。

如果还没有排好序,你懂的。下面是个例子:

4 , 7 , 9 , 6 , 5 , 5 , 2 , 1 ( 未排序 )

2 , 5 , 4 , 7 , 5 , 9 , 6 , 1 ( 随机排列 )

1 , 4 , 5 , 6 , 9 , 7 , 5 , 2 ( 再次随机排列 )

1 , 2 , 4 , 5 , 5 , 6 , 7 , 9 ( 天呐,真幸运 )


你不停地随机排序,直到得到一个有序数组。

毫无疑问这是最低效的排序算法之一,除非你非常非常幸运。它时间复杂度是令人窒息的 O(n!),而且随着元素数量增加,很有 O(∞) 的趋势。

量子 Bogo 排序(Tyler Schroeder 的回答)

我是量子 Bogo 排序的粉丝:

  • 随机排列数组中元素。

  • 如果数组没有排好序,摧毁当前宇宙(这一步就拜托你了)

  • 存活的宇宙将会有排好序的数组。 时间复杂度仅仅 O(n) 注意:这种算法依赖于量子力学的平行宇宙理论的可靠性。如果量子力学的平行宇宙理论不准确,这个算法时间复杂度达不到 O(n)

打印店页码排序 (Yi Wang的回答)

这并不是我发明的,我从别处看到的。

一个学生去打印店打印材料。他需要两份,但并没有直接打印两份,而是将每一页打印了两次,像下面这样:

需要的页码顺序: 1 2 3 4 … N; 1 2 3 4 … N

手上的页码顺序: 1 1 2 2 3 3 4 4 …. N N

他开始对打印材料排序,取一页放在左边,然后取一页放在右边。打印店老板看不下去了,直接把材料拿过来。

老板首先取一页放在左边,然后两页放在右边,再然后两页左边,两页右边…… 排序速度瞬间翻倍 ……

(有网友评论提醒:这是归纳,不是排序)

下面是其他网友的回答:

慢排序

这是一个非常幽默却没什么用的排序算法。它基于“合而不治”的原则(分治算法基本思想“分而治之”的反义词,文字游戏),它由 Andrei Broder 和 Jorge Stolfi 于 1986 年发表在论文《Pessimal Algorithms and Simplexity Analysis(最坏排序和简单性分析)》中,伪代码如下:

function slowSort ( array , start , end ){

if ( start >= end ) return ; //已经不能再慢了

middle = floor ( ( start + end ) / 2 );

//递归

slowSort ( array , start , middle );

slowSort ( array , middle + 1 , end );

//比较得出最大值放在队尾







请到「今天看啥」查看全文