比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

作者:admin   发布时间:2021-10-09 22:51   浏览:
正文

本文经AI新媒体量子位(公多号ID:QbitAI)授权转载,转载请有关出处。

程序bug也能负负得正吗?

还真能够。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

比如程序员们再熟识不过的排序算法,议定两个“bug”居然能歪打正着,实在令人匪夷所思。

请望这位程序员写的数组升序排序代码:

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

今天这串代码在Hacker News论坛上骤然火了首来,引来大批程序员围不悦目。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

乍一望这段代码,你的响答会是什么?会不会觉得这个程序员程度太差了,连基本的冒泡算法都写不益:

不等号倾向错了,第二层循环指数j的周围也弄错了。

总之,这段代码“绝对不能够切确”。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

△冒泡算法

但倘若你真的运走一下会发现,效果还真的是依照升序排列的。

吾们再来望一下切确的冒泡算法代码是怎样的:

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] 

后者分歧之处是j = i + 1且A[i] > A[j] ,两段程序云泥之别。

然而吾要通知你一个不走思议的原形,其实第一串代码是对的,而且能够厉格表明。

那么它是如何实现切确排序的?

为何能歪打正着

仔细一想,其实很容易理解。由于该算法比冒泡排序多一半交换操作,正益能够将降序编程升序。

不过,作者照样给出了厉格的表明。

吾们定义Pᵢ是经过i次(1 ≤ i ≤ n)外循环后得到的数组。

倘若算法切确,那么前i项已经是升序排列,即A[1] ≤ A[2] ≤ . . . ≤ A[i]。

表明该算法切确,实际上就是表明Pₙ对于任何n都成立。

根据数学归纳法,吾们只要表明P₁成立,倘若Pᵢ成立,接着再表明Pi+1也成立,命题即可得证。

P₁隐微是切确的,而且这一步和清淡的冒泡算法降序异国区别,经过第1次外循环,A[1]就是整个数组的最大元素。

接着吾们倘若Pᵢ成立,然后表明Pi+1成立。

吾们先定义一个序数k:

最先倘若A[k](k介于1~i之间)已足A[k]>A[i+1]最幼的一个数,那么A[k−1]≤A[i+1](k≠1)。

倘若A[i+1]≥A[i],那么如许的k不存在,吾们就令k=i+1。

考虑以下三栽情况:

1、1 ≤ j ≤ k−1

由于A[i+1]>A[j],异国任何元素交换发生。

2、 k ≤ j ≤ i (倘若k=i+1,则不存在此步骤)

由于A[j]>A[i+1],以是每次比较后都会有元素交换发生。

吾们操纵A[ ]和A′[ ]来外示交换前和交换后的元素,以是

A′[i+1] = A[k],A′[k]=A[i+1]

经过一系列交换,最大元素最后被放到了A[i+1] 位置上,正本的A[i+1]变成了最大元素,A[k]被插入了大幼介于正本A[k]和A[k-1]之间的元素。

3、i+1 ≤ j ≤ n

由于最大元素已经交换到前i+1个元素中,此过程也异国任何元素交换。

末了,Pₙ就是升序排序算法实走完以后的效果。

由于内外两组循环异国任何周围差别,因此这能够说是“最浅易”的排序算法了。

从代码上来望,它很像冒泡算法,但从表明过程中能够望出,这实际上是一栽插入算法。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

△插入算法

算法复杂度

隐微,该算法总会进走n²次比较,接下来计算算法的交换次数。

能够表明交换其次最多为I+2(n-1),最少为n-1。

其中I为初首数字的反序数,最大为n(n-1)/2

因此整个算法的复杂度为O(n²)。

从表明过程中能够望出,除了i=1的循环以外,其余循环里j=i-1之后的片面十足无效,因此能够将这片面省略,得到简化后的算法。

for i = 2 to n do for j = 1 to i − 1 do if A[i] < A[j] then swap A[i] and A[j] 

该算法缩短了比较和交换次数,不过算法复杂度照样是O(n²)。

网友:这个算法吾以前见过

比最容易理解的冒泡算法还要浅易,这个排序算法在Hacker News上很快引首了网友的围不悦目。

不少人觉得它“很眼熟”。

有位网友外示,本身曾在奥林匹克数学竞赛中望到一个同学用了一栽专门稀奇的排序算法,它能够运走但是效果很矮,更像是一栽插入排序。

倘若吾没记错的话,他用的就是这栽算法。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

原形上,关于这栽算法的商议已久,从2014年最先就不息有人发帖,这次作者将论文上传到arXiv后又引首了普及炎议。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

甚至还有乌龙事件发生。

有位网友扫了一眼论文就以为这个算法和本身10年前挑出的相通。

留言网友的算法:

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

乍一望两栽算法的代码实在很像,原理上实在有些相通。

都是望首来像冒泡排序,但其实更贴近选择排序。

不过很快有人指出原形:这栽算法中 j=i+1 to n,并且是当 A[i] > A[j] 时交换。

而作者挑出的算法中 j=1 to n,A[i] < A[j] 时交换。

两栽算法相比,网友此前挑出的更容易被理解为什么能够运走。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

自然也有歪楼的,有人就调侃本身刚学编程时写过这个算法。

吾百分百确定,在吾刚最先学编程、并想要找到最短的排序手段时就写过它。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的 比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

不过说到实际行使上,这栽算法必要的计算时间太长了。

有人就认为,这栽算法此前被发现过许多次,但是那些人根本没打算用它。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

也有人挑出:这栽排序异国就寝排序浅易。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的

就寝排序就是组织n个线程,让线程和排序的n个数对答。

例如对于[4,2,3,5,9]如许一组数字,就创建5个线程,每个线程就寝4s,2s,3s,5s,9s。这些线程睡醒之后,就把本身对答的数报出来即可。如许等一切线程都醒来,排序就终结了。

但和作者挑出的算法相通,就寝排序由于多线程的题目,在真实实现上也有难得。

此外,这位网友也外示本身望到过这栽算法:

吾确定吾此前望到过这栽算法,它没著名字吗?

很快就有人挑议说——

倘若它没著名字的话,吾提出称之为“面试排序”。

比冒泡算法还浅易的排序算法:望首来满是bug的程序,居然是对的  

【编辑选举】

Gartner:33%的技术挑供商在两年内对人造智能的投资将达到100万美元以上 “脸书”回答宕机:误发一条指令!网友:这程序员不得祭天? Gartner:2021年新兴技术成熟度弯线中的 3大主题 35岁程序员为什么被嫌舍? 互联网工资贼高?送你一份程序员入走通知

热点文章
近期更新
友情链接

Powered by 国色天香社区视频高清 @2018 RSS地图 HTML地图