首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
华为云
V2EX  ›  JavaScript

阮一峰老师又被人怼了,这次是关于 JavaScript 的快速排序实现

  •  3
     
  •   cairnechen · 194 天前 · 22915 次点击
    这是一个创建于 194 天前的主题,其中的信息可能已经有所发展或是发生改变。
    起因是 ideawu 发微博吐槽几乎所有的前端面试者的快排实现都是阮一峰的错误版本。

    v 友们怎么看这个问题?

    完整分析见 https://juejin.im/post/5af4902a6fb9a07abf728c40
    194 回复  |  直到 2018-07-26 14:58:35 +08:00
    1  2  
        101
    murmur   193 天前   ♥ 1
    @DOLLOR 虽然有黑的嫌疑,但是的我自己都感觉前端处在程序员最低端
    要么天天造轮子 要么天天换轮子
    java 一个 spring 基本统治半壁江山那是帝国级别的啊
    前端还在玩三权分立配在野党涉政
    要么解决同行的坑 尤其是库克掌权的苹果各种 bug 满天飞
        102
    murmur   193 天前
    @h1367500190 一个标签要不要关闭又不是什么值得自豪的是 无非是他习惯了 xml 写法还是接受了很 geek 的写法
        103
    ryd994   193 天前 via Android
    @zhicheng “记住的应该是 a^2 + b^2 = c^2 而不是 a^2 + b^2 = c^2 的证明过程。”
    你可以看看大厂有哪个不考算法的
    结论可以直接用
    证明过程可以网上查

    但是不靠记忆,自己推演出证明过程,这才是真能力
    不然遇到个稍微改版的问题,还背书生搬硬套,立马看出水平来了
        104
    congeec   193 天前 via iPhone
    太可怕了,我要努力早日脱离前端
        105
    zhicheng   193 天前
    @ryd994 我并没有说大厂不考算法,我说的是考快排这种东西并不能起到考察候选人的作用。

    自己能推演出证明过程?只不过是理解了别人的过程,然后方便记忆了尔已。换个说法,如果面试考的不是快排,而是证明年顿三定律,你会不会觉得这个是背下来的?
        106
    BXIA   193 天前 via iPhone
    快排太慢了。给你们个 O ( 1 )的
    For i in list
    Switch(fork())
    Case 0:
    Sleep(I)
    print(I)
        107
    DOLLOR   193 天前
    @murmur
    ✖️ 前端 vs java&spring
    ✔️ 前端(vanilla + vue + react + jquery + angular ……) vs 后端( java&spring + php&thinkphp + node&Express + python&Django + Ruby on Rails + C#&.NET + go&beego ……)

    这么一看,轮子多才是常态嘛……
        108
    ryd994   193 天前 via Android   ♥ 1
    @bucky 你可以说他们不是好老师,但你没权利说他们没用。有人擅长创造知识,有人擅长传播知识,技术高没用,你真牛逼。人家的技术不是自己学的

    让你多看书这很正常。让你 rtfm 并不是不尊重你,而是因为 rtfm 就是最靠谱的方式。你可以说他们说话不客气,但是这改变不了要 rtfm 的时候就该 rtfm 的事实。

    三层小楼,你说请教我造顶楼的技术。对不起,没有,一二层你一定得造,而且得造稳。网上各种教程最大的问题在于,他们一二层只搭脚手架。然后给你看看顶层多好看。

    说实话网上的教程当消遣看看得了。本来就不该要求有什么干货。真的干货能写一本书,一篇文章怎么能解释透。
    第一靠谱的是源码,其次是官方文档,再其次各种二手翻译文档,最不靠谱的就是各种博客。
        109
    ryd994   193 天前 via Android
    @zhicheng 你非要觉得我是背过程我也没办法。你这个想法就和那些刷 leet code 还要吹嘘自己刷几遍一样。
    没见过的问题,能独立解决,这才是我上面说的能力。

    就拿快排做例子,基本的快排背下来不难。那要是要求变一点呢?比如只要找到前 N 个元素。或者要求并行化。

    举一反三,再反三。反的过程才是本事。不存在背这回事。或者你要说这也是背的话,那过去未来,所有的知识和研究,那都是背。
        110
    zhicheng   193 天前
    @ryd994 什么时候流行不看别人的内容就随便瞎怼了?

    你说的能独立解决问题,能举一反三,都和会不会快排没有一毛钱关系。我说的还是,考快排并不能考察这个人的能力。

    你要说你能通过快排推导出整个世界,通过快排能计算出股票趋势,那是你的本事,和我说的无关。
        111
    lsmgeb89   193 天前   ♥ 2
    阮一峰并不是科班出身,写的不好很正常。

    没有经过正式算法训练的,这些小地方没有注意很正常。

    只是他的博客比较出名,树大招风了。

    不过有错误指出来,改正就好了。
        112
    nexusone   193 天前
    阮一峰一直在传播知识,谁都会犯错,指出来就可以了,再吵吵你是想说你是有多牛逼嘛
        113
    ryd994   193 天前 via Android
    @zhicheng 你一边说考快排没用
    一边又说,应该背的是证明的结果而不是过程
    所以你说考什么吧。
    在我看来,问如何使用某某函数,这才是真的“茴字有几种写法”

    我想说的是,无论结果还是过程都不应该背。而是应该锻炼思维能力。考基础快排怎么写,证明面试官水平有限。面试怎么不可以考快排了,一步一步接着问下去。如果加上 xx 限制,怎么办?如果在某某机器上实现,该机器的性能有如下特点,怎么办?快排就是个引子。知不知道快排,都可以接着问下去。
        114
    zhicheng   193 天前
    @ryd994 you are right.
        115
    Esen   193 天前 via Android
    阮一峰是经济学博士,非计算机科班出身,别太较真。
        116
    bucky   193 天前
    @ryd994 麻烦你看清楚我说的内容再回复我好吗,我说的明明白白,你技术高表达不出来是对别人没用,我没说没用。

    首先你要区别什么东西适合做教程,文档是用来查的,根本不适合教程,源码就更别说了,代码是综合知识的产物,你真这么自信能吸收别人的源码?就算你能吸收,我也不认为这效率有多高

    一说教程就推荐文档,书籍,甚至源码,绝对是走火入魔,反正你看完书,看完文档,看完源码真正吸收了多少,你不说也没人知道,这个 B 随便装也没人能拆穿你,这种陈词滥调,这种推荐的方式,外行都能搞,和公众号文章写文章区别

    当然你可以我们低级,我们水平低,反正我们这类人从小被打击惯了,见怪不怪,都是我们自己错。

    爱因斯坦都说了,你把知识无法解释给小学生听,就说明你自己理解的也不到位,人家爱因斯坦也没说你们智商低,给你们说就是对牛弹琴。
        117
    grzhan   193 天前
    看了下楼里评论,然后把这事拿出来和周围人讨论了下
    感觉阮老师的风评现在两极分化还蛮严重的( x
        118
    ryd994   193 天前 via Android
    @bucky 读书无用论,我不会我有理,理直气壮,佩服佩服

    看完源码吸收多少不好说,提个 pr 还是可以的。外行连书名都不知道,内行至少告诉你个关键字。有个关键字能省 99%的时间。
    临时急用,网上抄一段交差,那也就算了。但是出来混,迟早要还的。所谓背技术债。一直不懂,出了 bug 谁来修? stackoverflow 么?

    不难发现,越是一天到晚变的语言,喜欢这样速成的越多。因为钻研下去也是白搭,反正很快就要重写的。怎么不努力提高水平,多提几个 pr ?

    不妨看看 C 程序员们、底层开发们、计算理论研究者们、算法研究者们,有速成的么?

    说前端水,不是因为前端这个领域容易,而是速成的太多,以至于水平深浅都看不出来了。
        119
    bucky   193 天前
    @ryd994 额,你这阅读理解能力,竟然能想到读书无用论,不知道你从哪句话里面看到我反对读书了,我只是说有些人真本事没有,真正回答问题一个都不会,就知道推荐书籍,让别人读源码看文档,这种废话谁都能说,都不需要懂技术。

    你这阅读理解能力,真怀疑你平时看书能吸收多少,我反对就是你这种人,可能连写一篇博客的能力都没有,就过来批评别人了,你后面说的话在我看来完全是文不对题,恕不奉陪,怕了,怕了
        120
    THP301   193 天前
    何必放大别人犯下的一个小错误呢,装得好像大家都是完美的人生那样,4 个字形容下现在的装 X 人士,恶心至极!
        121
    Telegram   193 天前
    只能说不是最优解,不能说错误吧。
    还不是一样能实现功能
        122
    agagega   193 天前
    别的不感兴趣。就想知道,阮老师或多或少也被怼了这么多次了,他回应过么?知错能改没关系,但是闷头不说话就有点那啥了。
        123
    ltoddy   193 天前
    说实话,阮写的东西太基础,而且也没什么能够让你提升的东西。
        124
    alamaya   193 天前
    @bucky 我觉得你的表达能力有问题,不适合写博客
        125
    naeco   193 天前
    树大招风
        126
    bucky   193 天前
    @alamaya 对呀,我没写呀
        127
    mulog   193 天前
    感觉能写出这个错误实现的面试者,真的就是纯背诵选手啊。。
    哪怕你本来不会,为了准备面试学几个常见算法,你好歹 wiki (哪怕百度吧。。)一下能看到时间空间复杂度分析,你再看看这个实现难道看不出有问题么。。
        128
    orangeade   193 天前
    @murmur #101 safari 是真坑,今天还看到微博 pwa 的开发者吐槽 iOS 的 safari 上使用 pwa 的 bug
        129
    wizardforcel   193 天前 via Android
    非原地快排就是这样,不爽就不要玩。

    另外,每个调用里面的扫描从一次变成了三次,所以时间复杂度并没有增加。
        130
    ryd994   193 天前 via Android   ♥ 1
    @bucky 呵呵,举个例子,Nginx SSL
    很常见的问题吧
    如果你百度,搜到的博客教程一多半都有 ssl on;
    然而只要看看文档,就会发现
    http://nginx.org/en/docs/http/ngx_http_ssl_module.html#ssl
    It is recommended to use the ssl parameter of the listen directive instead of this directive.

    如果你查 nginx 判断文件存在,百度一下
    有一多半的人说用 if -e
    呵呵: https://www.nginx.com/resources/wiki/start/topics/depth/ifisevil/
    当然,现在搜,可以看到很多说 try_files 才是正解的,那是因为这个问题实在太久了。官方文档终于扩散到百度知道了。

    如果你问 Nginx 怎么加 SSL,有人回答
    rtfm: http://nginx.org/en/docs/http/configuring_https_servers.html
    我认为这是很友善的回答
    如果你问怎么判断文件是否存在,有人回答
    rtfm:try_files
    我认为这是非常值得感谢的回答,因为这是对的!错的答案除了表达虚伪的关心,还不如不答。一大段 if -e 配置只会污染信息。

    你连自己的领域都不认真钻研,那就永远只能吃人家剩下的。

    如今互联网上,最不缺的是不知真假的信息,最缺的是正确而及时的信息。那么哪里的信息最正确呢?源码、文档。

    看教程救火可以。但是不看源码不看文档,不钻研不行。谁不是一步步走过来的?看个文档有多难?

    源码有时候是不得不读。因为连文档都跟不上。你上网搜 Linux TCP 栈,绝大多数都是 2.x 的。Linux 内核都 4.17 了好么。不读源码还有选择么?

    阮一峰的博客我也看,吃早饭的时候就当娱乐一下。但是认真要用的东西,我只看官方文档。因为迟早还是要看的。
    教程我也看,但是里面的每一行代码,我都会参照官方文档。
    文档,是永远避不开的。
        131
    ryd994   193 天前 via Android
    说到底,这锅还是他自己背。不写 errata
    错了就错了呗,还留着误人子弟,还留着被人一遍遍的怼。
    都这么多年了,被怼了这么多,还能坚持不改。是真牛逼。
        132
    ryd994   193 天前 via Android
    @bucky 希望你今后在饭店吃饭,不要给差评,因为你做不出一样的菜
    希望你今后在淘宝买东西,不要给差评,因为你没有开店买一样的东西
        133
    bucky   193 天前
    @ryd994 我已经表达的很清楚了,教程和文档的功能不一样,你非要理解成我不让大家看书,看文档,看源码,那就没必要说什么了,基础的理解都是错误的,还有什么讨论的必要,根本没在一天线上,讨论就是浪费时间
        134
    ryd994   193 天前 via Android
    @Telegram 功能是实现了啊
    O(n^2) 的话还不如用冒泡
    至少代码简单,小学生都懂
    而且内存占用还小呢!
        135
    misaka19000   193 天前
    现在大部分的前端的真正水平大家都懂的,心里面明白就行了
        136
    bucky   193 天前   ♥ 3
    @ryd994 你这种人的存在就是我维护阮一峰的原因,思路混乱,理解能力差,脑子里装了几个大词时不时蹦出来,自己都不知道自己表达什么,和你交流就是浪费时间
        137
    ryd994   193 天前 via Android
    @bucky 对啊,阮一峰放个屁也是香的。
    原文还在呢,至今不改,至今不提醒别人。
    管坑不管埋。
    这样的垃圾文章,到底是帮人还是害人。

    话说回来,要是没人怼他,这段代码是不是就此流传开去呢?哦,现在有这么多人怼过,依然在继续流传。

    明明有正规的算法入门教科书,快排就是一个小章节而已,看完用不了一个小时。到底是谁理解能力差呢?
        138
    ryd994   193 天前 via Android
    @bucky 你这就和维护伪科学的人一样。
    你们正规科普宣传没有做到位啊,至少他们讲的我们能看懂。
    为了一点尊严可以颠倒黑白
        139
    20015jjw   193 天前 via Android
    @bucky
    “...可是没有表达能力,技术高对他人有什么作用?上学的时候就有许多这种老师,知识深厚,讲课屁都不通...”

    所以你宁可要菜的老师生动形象简单易懂地把错误的知识传播给你 也不喜欢让强的老师用比较枯燥的方式教授正确的知识...
    不得不服...

    看你回复挺尴尬的.. 我就随便戳个漏洞.. 其他不多说..
        140
    zhicheng   193 天前   ♥ 2
    @20015jjw 看你的回复也挺尴尬的,

    技术高的老师有表达能力好的,也有表达能力差的。
    技术菜的老师知识有讲错的,也有讲对的。

    为什么你就钻到那个牛角尖里了呢?为什么就觉得对方就喜欢菜的老师,对方喜欢错误的知识呢。对方明明讲的是用生动形象的方式传播知识是更好的方式。
        141
    tschenhui   193 天前
    这让我想起了一个类似的事情,主角是,武志红。两件事很类似吧,我吧之前的事件看法,平移套用到这件事上来,大家可以对我的看法观点批判性的借鉴。首先,阮一峰大部分精力都在技术的传播方面,是一线开发者还是技术讲师,当然是后者了。术业有专攻,专攻讲课的人,在技术细节问题上有错误,这件事是难免的,也是可以理解的,前提是以客观的态度,有则改之无则加勉。如果以“就算错了,也要怼回去”的态度对待,就不好了。其次,技术圈子如果看成是一个生态系统的话,是缺少纠错机制的,一个人肯定不是事事皆正确,但名气大了,谁来给他纠错呢?名气更大的人物?这不具可操作性,只能靠术业有专攻,之中,专攻那个点的人来纠错,但这样的人,往往不具有太强的号召力和传播性,至少和以传播见长的人相比,就好像这次事件中的主角们。回到问题上来,没有给阮一峰这类人建立纠错机制,不是这些人自己的问题,而是缺少一个系统框架,这壳不是什么 thinkphp 框架,而是一种社会协作框架。框架搭得好,每个人都能各就其位,各司其职,传播技术的搞传播,细分领域的大牛可以对正确性进行监督和纠正。
        142
    ryd994   193 天前 via Android
    @zhicheng 可现在某些人就是这个论点
    阮一峰 vs 正规算法教材

    如果某些知识无法用简单的语言说明,那我宁可死啃正确的原版,然后承认自己真的看不懂,也不愿看错误的简化版。
    可惜,在看完原文之前,没人能识别简单的版本是否正确。

    简化版看看娱乐一下还是可以的。想学到干货还是算了。
        143
    ryd994   193 天前 via Android
    mmm
    何其相似

        144
    bucky   193 天前   ♥ 1
    @zhicheng 你先别急着尴尬,如果别人讲的清楚,即使有错误,你也能发现, 而讲不明白的,你连发现错误的机会都没必要,老师的作用从来都不是字典,不是标准答案,否则直接交给机器人不就行了,要什么老师?在学习的路上,有错误从来不是什么大不了的事情,发现不了错误才是
        145
    quintic   193 天前   ♥ 10
    我觉得作者可能没弄清楚*渐进*复杂度的意思:只测一个点的速度没有任何意义,要看 N 趋近无穷时的渐进行为。

    删掉文中 const arr = []一行代码,我们生成若干长为二的幂次的数组并测试,

    for (var i = 12; i <= 24; ++i) {
    arr = [];
    generateArr( Math.pow(2, i) );
    console.time('N = 2^' + i);
    quickSort(arr);
    console.timeEnd('N = 2^' + i);
    }

    我得到的运行时间如下:

    N = 2^12: 8.030029296875ms
    N = 2^13: 5.56005859375ms
    N = 2^14: 9.332763671875ms
    N = 2^15: 20.909912109375ms
    N = 2^16: 38.673828125ms
    N = 2^17: 89.992919921875ms
    N = 2^18: 187.841064453125ms
    N = 2^19: 321.177001953125ms
    N = 2^20: 683.663818359375ms
    N = 2^21: 1461.80908203125ms
    N = 2^22: 3129.0927734375ms
    N = 2^23: 6694.160888671875ms
    N = 2^24: 14762.876953125ms

    可以看到,从 2 的 14、15 次方开始(约一万),数据规模每乘 2,运行时间也乘 2 左右,符合 N log N 在 N 趋近无穷时的增长速度( lim n->inf (2N log 2N) / (N log N) = 2 * lim (log 2 + log N) / log N = 2 * 1 = 2 )

    因此,阮一峰的实现达到了快排的渐进时间复杂度,没有问题。(其实我个人偏好这种损失一定常数,但保证简洁正确的写法)
        146
    zhicheng   193 天前
    @ryd994 从你们喷的点上,我并不认为阮一峰的算法是错的,你可以说有更好的写法。但用 JavaScript 实现快排本身就很娱乐了,本身也是一个演示级的东西。

    学知识本身就是循序渐近的过程,你非要别人一口吃个胖子也不现实。你可以说很多看阮一峰文章的人没有质疑能力,没有深入学习的能力,但你不能说入门文章没有意义。

    用一个文绉绉成语表示一下就是,你们有点儿吹毛求疵了。
        147
    20015jjw   193 天前 via Android
    @zhicheng 话不多说 参考#143

    不知道你们这东西有什么好洗的 错的就是错的啊 居然还能强行 defend 说这个答案宗旨上是对的...?还表达清晰...?面试我要看到这种直接拒好吧... 这算法名字就叫 quicksort 写出 n^2 还有理? prod 里会写 quicksort 可能没那么重要,但是对于语言自带操作的理解是很重要的,不然小小一行在大厂可能就是六位甚至七位的电费...
        148
    zhicheng   193 天前
    @20015jjw you are right.
        149
    quintic   193 天前
    @20015jjw 不是,朋友,阮写的是对的,复杂度是 n log n 不是 n 方,是你搞错了。

    实测的支持你可以看我的回复 145 楼(如果是 n 方,n 每乘 2,时间应该乘 4,但实际是 2 )

    分析的话是这样:splice 是要过一遍数组,但是是传到那个函数调用的 arr,不是大的 arr,所以他只是多过了一遍当前区域的 arr 而已,而快排本来就要过一遍当前区域来筛出小的和大的,所以这里损耗的是一个常数(一遍和两遍的区别,你看原文给出的数据也是 5 秒 vs 10 秒,就是差一个常数 2 )

    很奇怪怎么会吵了一百多楼还没搞清楚……
        150
    YenvY   193 天前
    你们是觉得大 V 级的 blogger 有必要为自己的文章的后果考虑,有错就改,最好还能把评论区只会喊 666 的人挨个艾特一遍,否则不是人血馒头也是误人子弟,像阮这样的大概会被评个“前端教育界模范和罪人”?
    还是说只要写博客就相当于承诺了上述那些东西;
    还是说这些狗屎都是闲的蛋疼的人才去提起,老子承认错误,想改就改,我又没说我的播客要教你什么东西,我凭什么要负这样那样的责任
    说到这里我就想请教诸位了,有没有相关的可以引用的文档可以显示的说明自己的博客 /Repo/Project 一不保证正确二不保证改正,欢迎 PR/评论 /参与维护,也欢迎给我打钱买咖啡,但只是当作对以往工作的肯定,我还是坚持前两点。这种为了懒和不用负责任的东西总会有人提前想到的吧
    反正围绕阮老师的论战一年有好几轮,我觉得可以存在这样的一份文档,如果有共识就趁早文档化,省的总拿这些事儿抬杠,还没人用淋语,特别没观赏性
        151
    nikolai   193 天前
    还不是因为背题就可以过面试,成本低收益高,大家就去背了
        152
    tsui   193 天前
    原文作者本科基础也不行啊,刚开始 O(1)复杂度那个例子,他不知道什么是 loop unrolling 么
        153
    vindurriel   193 天前 via iPhone
    @davinci 你说的对 左耳朵耗子的评论错了 平均时间复杂度不是 n2
        154
    zhaoweichen   193 天前
    @EmbraceZ
    @wizardoz 说的没问题,尾递归优化有条件 (比如,能转换成用循环的实现)。
        155
    zhaoweichen   193 天前
    想了半天也没想明白阮老师的写法怎么就 O(n^2)了...
    @davinci @vindurriel 要不是看你们评论,我还以为我算法白学了 :)
        156
    zhaoweichen   193 天前
    @tsui “完整分析”里面,O(1)那个例子不是循环啊。
    问题应该是对输入规模的理解问题。第二次的输入也没超 64bit...

    话说,我没接触 javascript 的类型系统,javascript 是像 python 那样无限精度的么?还是说弱类型系统可以根据输入推测类型?
        157
    zhaoweichen   193 天前
    @quintic 平均时间复杂度的确没问题,但是空间复杂度差了很多。
    如果很多这样的程序在浏览器里跑,就算时间复杂度没问题,系统性能也会受影响嘛~
        158
    binux   193 天前
    @BXIA #103 你这明明是 O(n) 的
        159
    markx   193 天前
    我感觉,splice 是为了遍历时排除掉 pivot, 开新数组来递归也没问题啊。 这样的写法虽然空间上效率不好,但是确实更容易看懂,作为教程是很好的。 而且,我也不觉得这个实现是错误的。我认为快排的关键是 pivot 和 partition,这个这两点这个实现并没有搞错。

    错的可能是,大家把教程代码当做工程代码了。
        160
    tsui   193 天前
    @zhaoweichen 中午粗看了一眼以为它用循环次数来说明什么
    重看了一眼不明白它这函数到底干啥了
    function increase(n) {
    n++;
    }
    连个 return 都没有而且 javascript pass by value 啊
        161
    q397064399   193 天前   ♥ 1
    一帮傻小子 又在这里 搞算法之争,,老板都拿钱玩嫩模去了,
    你还在这里讨论着算法来算法去,加工资了吗?买房了吗?有女朋友了吗?

    又不是搞数学证明,对工程师来说算法会应用就好了,
    大致有个概念 什么场景用什么结构 ,像部分数据结构 红黑树 多线程 怎么加锁 解锁,
    在不同场景下 能分析各种数据结构跟优劣就好了。实现?你怕不是脑子进水有病。
    都 21 世纪了,兄 dei,现成的库一大堆,人家几十年的软件工程实践让你当狗屎吃了?

    另外书上描述的算法伪代码又是一大堆,什么时候轮到你去发明新算法 并做数学证明的时候
    再来跟我讨论算法问题。

    最后哔哔一句,工程师仍应该以实践应用为主,
    算法 应该在有需要算法应用的场景的时候再去做详细了解,
    另外排序算法真的不算什么,它只能解决某一类的问题,根本没办法证明开发者的能力
    工程实践中 很多金融类 数学类 的计算算法 描述起来比你这个复杂多了,
    需要足够深的领域知识才能弄明白,你也没见人家出来哔哔 我这个算法 这么难实现,逻辑多么复杂
        162
    uolcano   193 天前 via Android
    1.前端大多数是自学的,要求各个都是科班出身,把 C 和数据结构的课先补上,但是不现实,大家都只是为了赚钱糊口; 2.阮一峰写博客的目的主要在于自己学习和知识管理,只是把个人的学习笔记放到了网上,那些重点在于喷而不是讨论存在哪里改怎么改的人的学习笔记能否拿出来让大家“彰仰”一下; 3.国内的技术圈风气是不是吸收了太多了微博的风气,不讲分享和沉醉于技术身,而只是为了站队与相互攻击,一盘散沙; 4.能够多一点大牛分享知识,也就可以减少非科班出身的博主“误导人”的事情发生了,不应该要求网上信息的绝对纯净,而是提高信噪比,如果“大牛”们能把更多精力放在“正统”技术的传播和分享上,而不是把一个问题扩大到对某个群体的攻击上,将是善莫大焉的; 5.撕逼是最具有热度的事情,不知 v 站是否对发高热度贴的 po 是否会有奖励,传统媒体、自媒体、社交媒体最喜欢玩这套了,屡试不爽。
        163
    ucando   193 天前
    其实算法本身的思想是没毛病的, 只是缺少了一些优化而已
        164
    sunnogo   193 天前 via Android
    博客是来一起学习的,有错误正常啊。怒怼啥的好搞笑啊。我很喜欢阮一峰的博客。
        165
    lynx   193 天前
    实现细节虽然性能差点,但是核心的东西没毛病,比如 haskell 官方这样写的:

    quicksort :: Ord a => [a] -> [a]
    quicksort [] = []
    quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
    lesser = filter (< p) xs
    greater = filter (>= p) xs
        166
    lukefan   193 天前
    阮一峰的文章是很多年前的吧

    很早前 IE 下字符窜不允许下标访问, 他那种方法拿去套 duck typing 不容易出错
        167
    AlphaTr   193 天前
    快排核心表现在快上,具体是两方面,平均时间复杂度 O(nlogn),空间复杂度 O(1), 实现空间复杂度是通过原地交换做的,通过开辟新数组并不能实现 O(1) 的空间复杂度; O(nlogn) 是包含一次二分查找的,就是代码实现的数组下标方式,通过 splice 和数组下标区别在于 O(n) 和 O(logn);所以阮版本只能说实现了一个效率比较低的排序,有快排的形式,没有快排的效果;说写错了也不为过
        168
    koc   193 天前 via iPad   ♥ 3
    阮一峰没有错,他只是在写文章,从来没说自己绝对是正确的,也没有禁止别人指出来
    指出来的人也没错,技术问题,对了就是对了,错了就是错了

    真正有问题的就是那些阴阳怪气嘲笑阮一峰水平的人,和那些觉得“阮一峰这么努力你们怎么能指出他的错误”的人
        169
    gnaggnoyil   193 天前   ♥ 3
    楼上很多人对阮一峰文章中的事实错误和潜在误导的辩解完全可以原封不动地用在谭浩强身上……
        170
    zhaoweichen   193 天前
    @tsui 目测是想表达 O(1)情况下,输入 size 不一样,消耗时间是同等级的。但是文章里拿的两个数,都是没超 32bit... 很值得吐槽...
    如果是 python 的话,long 的长度可以变化,倒还可以拿一些数字来做测试,但是高精度加减复杂度肯定不是 O(1)。

    总之这个例子举的非常失败... 另外,作者底层的知识堪忧...
        171
    zhaoweichen   193 天前
    @ryd994 难道是蛋友? 今儿刚从无聊图里看到这张 :)
        172
    vindurriel   193 天前 via iPhone
    @zhaoweichen 这是个文化的问题 目前的讨论氛围是 专家不能犯低级错误 犯了错也不能承认和改正 一定要把名誉赌在这种随时、人人都可能犯的错误上

    比较理想的讨论氛围应该是 公众允许犯错(包容同情) 专家有错就改(谦虚尽责)
        173
    plqws   193 天前 via iPhone
    阮一峰的博客说白了就和《教小学生学编程》那种科普读物一样,用最简单的语言最容易被人理解的方法去输出知识。阮一峰博客的黑点多了去了,随便举个例子,复杂度从来不强调是时间还是空间的,一切都靠猜。但是一样不能影响我在面试前夕靠阮一峰的博客刷知识点,因为想要看懂超容易,至于有没有错不会自己以后去考证吗?
        174
    sengxian   193 天前
    吐槽 O(n^2) 的人自己都不懂快排
        175
    SPACELAN   193 天前
    @gnaggnoyil #169 这个年代没多少人知道谭浩强了
        176
    ToT   193 天前
    @wubinbin0403 同意。他的不是最优解,但是已经实现了快速排序的原理。同样的写法可以实现 merge sort 也会出现空间复杂度高的问题。
        177
    TZ   193 天前
    被怼排行榜名次应该不错了
        178
    youxiachai   193 天前
    @ryd994 你这话...说明你也是跟大流的...
    原文评论..早就有相关讨论了..
    这是这次..很多人看到标题就开喷了..
        179
    marcong95   192 天前
    其实随便定性分析一下,阮的代码还是 O(nlogn)的:

    [arr.splice O(n) + for 循环 O(n)] * 整个递归 O(logn)
    = 2O(n) * O(logn)
    = O(nlogn)

    说啥 in-place 的,快排的定义里我记得是没有 in-place 的说法的。中文 wikipedia 上还有非 in-place 实现的伪代码,也是开的两个数组,各种 one-liner 的快排里面开两个数组也是很正常的。文中「标准的快排只需要原地交换即可」肯定不准确,而且非 in-place 的快排还可以实现稳定排序。
        180
    mengyaoss77   192 天前
    快速排序, 写起来很快速 思考起来也快速的 快速 double 排序算法 ! yeah
        181
    skadi   192 天前
    丰富了我的 block 列表...(吃瓜
        182
    zhaoweichen   192 天前 via Android
    @vindurriel 基本赞同,不过我更觉得很多人态度有问题。哪里都有 troll,但是好像中文论坛里戾气重,更容易吵起来。
    不管是不是专家,只要能心平气和的码字,有想法就说+举反例或者证明,气氛肯定会好很多的。但是感觉大家都没时间好好聊…
        183
    vindurriel   192 天前 via iPhone
    @zhaoweichen 不止中文社区 stack overflow 最近也在反思讨论风气的问题 https://stackoverflow.blog/2018/04/26/stack-overflow-isnt-very-welcoming-its-time-for-that-to-change/
        184
    Justin13   192 天前 via Android
    类似的问题我也遇到过,有个需求要用到小顶堆,在网上搜了搜,看懂算法就自己写了,写完后性能奇差。在 devtools 里调试了半天,发现大把的时间都花在了数组本身的方法上(slice,splice,push...)最后改完就和技术博客上的一模一样了。。。。
    其实算法是对的,问题在于实现,真正最好的实现就是 C 的版本,不要瞎几把改,虽然各种记下标很烦。
        185
    gogo81745   192 天前
    我觉得这种快排是没问题的。

    我自己写起来回是这样,思路跟阮一峰的一样。

    ![quicksort]( https://static.gogo.moe/files/2018/05/quicksort.jpg)

    为什么会写出这样的代码呢?

    实际上是在学 Haskell 的时候,看到 Haskell 那种简洁到可怕 快排,第一次见到这样的快排真的是被震撼到,太简洁了,太容易读懂了。

    ```haskell
    quicksort :: (Ord a) => [a] -> [a]
    quicksort [] = []
    quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSorted = quicksort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ biggerSorted
    ```
        186
    Codelike   192 天前
    阮师的博客多是基础之类,通常是翻译国外的博客所得。客观来说是一个乐于传播知识的、技术不是特别高的人。
        187
    binux   192 天前 via Android
    @marcong95 看英文版
        188
    iamdqncoder   192 天前 via Android
    @BXIA 你这个厉害了😄
        189
    mightofcode   191 天前
    这是什么傻逼文章
    阮一封的时间复杂度怎么就变成 n2 了
    不还是 nlogn 吗
        190
    tnter   191 天前
    今天博客被 dd 了,快排引发的血案啊
        191
    nvtag   191 天前
    说一句话啊,免费的东西,你们就不思考直接拿来学吗?你们这是在学习吗?还是做搬运工呢?做搬运工的那还是别搬了,终究是搬运工。
        192
    USNaWen   191 天前
    o(n)怎么变成 n^2 了。。。。也是醉了
        193
    marcong95   189 天前
    @binux 英文版看过了,的确没有非 in-place 的伪代码,不过也有谈及。而且英文 wiki 没有明确否认快排不能非 in-place。所以跟中文版并没有冲突。
    维基这种东西不同语言词条是独立的,也从来没有指引说以英文为准,我只是提供一个伪代码的来源而已。不要盲目否定中文内容好不好。
        194
    jasonbourne   117 天前
    恕我直言,阮一峰的那个复杂度也是 O(nlgn),只不过是原先的 2 倍,因为多了个线性表删除单个元素的复杂度,掘金的作者才是不懂装懂
    1  2  
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3747 人在线   最高记录 3911   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 27ms · UTC 06:34 · PVG 14:34 · LAX 22:34 · JFK 01:34
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1