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

阮一峰

人怼

快排

面试者

194 条回复 • 2018-07-26 14:58:35 +08:00

1 2

❮

❯

1

CoderGeek

2018-05-11 13:47:34 +08:00

日常被怼

2

seeker

2018-05-11 13:49:31 +08:00

怎么看？不看阮老师文章。

3

achilleo

2018-05-11 13:51:21 +08:00

看阮老师被怼（ 1/1 ）

4

changrui0608

2018-05-11 13:54:51 +08:00 via Android

看完了帖子，怼算法的部分我觉得是没毛病的，阮老的快排写法我确实是第一次见...

5

xiaxiaokang

2018-05-11 13:56:05 +08:00

9

被怼是好事，说明生态很健康，最害怕知道是错却沉默

6

carlclone

2018-05-11 13:56:51 +08:00

帖子一堆前端的评论才是高潮

7

orangeade

2018-05-11 13:57:48 +08:00 via Android

阮老师昨天搬运 Google I/O 上关于汉堡和啤酒 emoji 的描述也是错的，芝士说成了奶油

8

changrui0608

2018-05-11 13:58:23 +08:00 via Android

不过原帖左耳朵耗子的说法也和我了解的不太一致，快排递归调用需要建立调用栈，空间复杂度应当是 o(logn)而非 o(1) (希望我没记错 xd)

9

lsvih

2018-05-11 13:58:31 +08:00

评论比文章更好看

10

owenliang

2018-05-11 14:00:30 +08:00 via Android

关我毛事

11

natscat

2018-05-11 14:04:35 +08:00

2

前端平均水平

12

wizardoz

2018-05-11 14:05:32 +08:00

我觉得可能是面试的公司泄题了，然后大多面试者都去百度了快排算法。
阮一峰这个实现确实不是典型的快排实现算法，有点像快排和合并排序的杂交版。
人有失手马有失蹄

13

nicevar

2018-05-11 14:07:32 +08:00

出点错指正就行了，没必要上升到嘴遁

14

EmbraceZ

2018-05-11 14:09:22 +08:00 via Android

@changrui0608 可以用尾递归优化的吧

15

lommo

2018-05-11 14:10:50 +08:00

说明大多数前端的数据结构还有算法基础都不扎实呗

16

leemove

2018-05-11 14:11:19 +08:00

不用标准的,阮一峰的快排,我都写不出来.....

17

murmur

2018-05-11 14:12:52 +08:00

1

不看这篇文章我还不知道快拍可以用 splice 操作

18

ycz0926

2018-05-11 14:14:34 +08:00

觉得下面的评论中肯些，一下子否定别人，这自信也是够了

19

whahuzhihao

2018-05-11 14:16:56 +08:00

其实思路是对的啊，比交换元素的那种写法更容易理解。

20

codermagefox

2018-05-11 14:17:14 +08:00

接受批评，我就是只知道看基本复杂度，面试就记几个排序和二叉树就去的菜鸡前端。
我写的虽然不是阮老师的版本，但是我也没去想过阮老师的版本是错的。

我承认我的算法能力很差。

非科班出身，希望以后有时间能补上来吧。当务之急还是工作重要。

21

wizardoz

2018-05-11 14:19:16 +08:00

@EmbraceZ 怎么优化也免不了 O(lgn)的栈占用，因为快排是由上往下拆分的，中间每一层的状态都得记录在栈中。

22

nosay

2018-05-11 14:24:26 +08:00

阮老师的博客一直有在追，受益颇多，说误人子弟，就比较过份了。

23

bucky

2018-05-11 14:28:38 +08:00

1

技术博客没有出现百家争鸣我也是很奇怪

24

wubinbin0403

2018-05-11 14:31:34 +08:00

实现快排的目的了吗？实现了。
最优解？不是。
错误版本?见仁见智。

25

samuel

2018-05-11 14:31:41 +08:00 via Android

看了下阮老师的实现，确实问题太大了…然而经常以阮老师的译文作为参考资料，不忍多黑

26

maichael

2018-05-11 14:32:49 +08:00

说明前端大多数人除了面试之外不会自己写算法。

当然，也说明了 CRUD Boy 和切图 Boy 永远占大多数。

27

VDimos

2018-05-11 14:33:21 +08:00 via Android

他还说过 docker 即将退出历史，还说过 webpack 这些打包工具即将成为历史。。。。

28

Leafove

2018-05-11 14:33:28 +08:00

从后面的评论来看在很多前端眼中阮一峰简直就是教皇,完全不能有丝毫不敬

29

rabbbit

2018-05-11 14:40:56 +08:00

额,当初好像看的是阮一峰的版本.问下,我这么有啥槽点 /错误吗?

30

aijam

2018-05-11 14:41:17 +08:00

硬广告时间： https://medium.com/@czheo/%E6%8E%92%E5%BA%8F-b5ef06533b11

31

zhicheng

2018-05-11 14:45:01 +08:00 via iPhone

1

本身就是演示一下算法，核心思想传达到了就 OK 了，难道真的有人用 JS 写的快排？要是纠细节，JS 执行要经过 parser 复杂度要不要算上？有些要做 JIT 复杂度要不要算上？

一定要能区分什么是拿来教育演示的，什么是工业生产使用的。

在我看来出题考快排的人本身就是错的，这东西除了背下来，别无他解，考验不了任何能力和智商（当然可能能排除一些记性不好的人，如果你提前告诉他要考快排实现的话。）。

32

alamaya

2018-05-11 14:47:40 +08:00 via Android

人非圣贤孰能无过，这篇文章有理有据有 code，也没啥问题吧。倒是有些人搞得跟偶像崇拜一样容不得别人说阮的半点不是，完全是在给阮招黑。

33

bucky

2018-05-11 14:47:41 +08:00

@maichael 那说说你平时用到什么算法

34

bucky

2018-05-11 14:57:14 +08:00

15

为什么大家拥护阮一峰，我也拥护阮一峰，因为许多人没有普及知识的能力，就知道嘲笑别人，除了推荐傻子都能发现的书籍，或者推荐让别人看文档以外没有一点有价值的东西，找别人的毛病倒是一套一套的，技术重要吗？重要，可是没有表达能力，技术高对他人有什么作用？上学的时候就有许多这种老师，知识深厚，讲课屁都不通，作为学生深受其害还没法宣泄，只能不断怀疑自己，而且我知道的几个编程大牛都在夸阮一峰老师，不知道那些批评的人什么水平

35

YenvY

2018-05-11 15:00:07 +08:00

本坛还有说阮吃人血馒头呢，这篇算是很好的纠错文了

要是换个跟阿里系血海深仇的老头子写篇文章来怼的话指不定写成什么样呢

36

carlclone

2018-05-11 15:01:58 +08:00

@zhicheng 你需要背不代表别人需要啊 , 这样就也做了一层筛选

37

chairuosen

2018-05-11 15:10:34 +08:00

作为一个前端，我面试人从来不问算法

38

CRVV

2018-05-11 15:11:09 +08:00

5

1. 用了 splice 说明他不怎么会写代码，不算错但是太奇怪了
2. 每次递归新建两个新的数组是正常的写法，其实就是 Python/Haskell 的著名的特别短的快速排序。这个版本很适合用来学习快速排序和递归，不是真拿来排序的。如果你觉得需要用背才能会写快速排序，那应该去看看这个
3. 快速排序之所以号称快速，重点是要在原来的数组里面做交换，这样的好处是很多操作都在相邻的内存上。JavaScript 没有数组，于是没有这个性质，所以 JavaScript 的快速排序应该不比堆排序快（我瞎猜的）
4. 因为 3，在原来的 Array 里交换，也不是正经的快速排序
5. 快速排序是一个很简单的算法（我认为比冒泡排序简单），根本不需要背，写那个短的 Python/Haskell 版本很容易，要把那种在一个数组里交换的版本写全对又不太容易。我觉得快速排序是一个合适的算法题

39

20015jjw

2018-05-11 15:14:19 +08:00 via Android

1

达不到 quicksort 的时间 /空间只能表示确实是完全错的有啥好洗.. 错了就认错呗..

40

aijam

2018-05-11 15:14:20 +08:00

@CRVV “ JavaScript 没有数组”是什么鬼

41

zhicheng

2018-05-11 15:15:47 +08:00

原来这么多聪明人，失敬了，如果不参考别的实现让我徒走实现一个完全正确的快排，我实现不了。你们都厉害的。

42

ipwx

2018-05-11 15:19:17 +08:00

@zhicheng 快排本来就是模板级别的算法。别人考信息奥赛的，初中就人人背得的东西，为啥成年程序员背不得？

43

ihuzhou

2018-05-11 15:20:20 +08:00

确实嘛，错了就错了，人家也没否定阮一峰的贡献。这种纠错精神值得尊敬。

44

izhulei

2018-05-11 15:21:06 +08:00

2

Q: 很多人批评你的技术文章，错误非常多，你怎么看？
A: 我一直是外行，从来不敢说自己是专家。对我来说，博客首先是一种知识管理工具，其次才是传播工具。我的技术文章，主要用来整理我还不懂的知识。我只写那些我还没有完全掌握的东西，那些我精通的东西，往往没有动力写。炫耀从来不是我的动机，好奇才是。
当然，我肯定只写那些我觉得对的东西，尽量对读者负责。但是没法保证，我觉得对的东西就是对的。网站流量越来越大，对我的争议也越来越多，好几次我都在文章前加上说明，这是初学者的笔记。我还会以这种方式写下去。我希望自己永远都能保持，那种不怕丢面子，敢于当众说蠢话的勇气。

45

wizardoz

2018-05-11 15:21:22 +08:00

@rabbbit 为啥你会用到 async await ？

46

zhicheng

2018-05-11 15:21:54 +08:00

@ipwx 我没说背不得啊，我是说这个东西没有考察候选人的作用。招人是干活的，又不是考奥赛的。

47

qiuyk

2018-05-11 15:22:41 +08:00

尴尬了文章中说快排最坏的时间复杂度是 O(nlogn)

48

ty89

2018-05-11 15:29:33 +08:00

嗯，确实写错了。那么应该把阮一峰烧死吗

49

rabbbit

2018-05-11 15:31:29 +08:00

@wizardoz
额,这个是以前写的算法动画里截出来的,拿 async 暂停.
想放上来问问算法有没有写错,没把无关代码删掉就发出来挺欠考虑的,抱歉.

50

CRVV

2018-05-11 15:32:34 +08:00

@aijam
JavaScript 的 Array 是 Object 而不是 https://zh.wikipedia.org/wiki/%E6%95%B0%E7%BB%84

51

dnxbf321

2018-05-11 15:33:57 +08:00

硬广一波 [https://github.com/dnxbf321/sort]( https://github.com/dnxbf321/sort)

52

realpg

2018-05-11 15:36:31 +08:00

其实挺好的
把那些不过脑袋只去搜索引擎搜答案的都淘汰了

53

chztv

2018-05-11 15:40:34 +08:00

@orangeade 确实是，看推上我也看到了，本来想回他的推，后来想想算了，这个也只能算是小问题。

54

chenyu8674

2018-05-11 15:41:05 +08:00

for(var i in list) setTimeout(function(){sortResult.push(i)}, i)

{doge}

55

janxin

2018-05-11 15:41:41 +08:00

面试中会面一些基础算法排序问题，很多人都是死记硬背，错了也不晓得问题在哪

56

hfpp2012

2018-05-11 15:46:40 +08:00

那些人嫌得蛋疼，出点错也是难免的，可能那些人是妒忌吧，毕竟他不如别人有名气，也要通过别人刷下存在感

57

chmlai

2018-05-11 15:47:18 +08:00

其实发现博文有问题, 直接在留言上指出来就行了, 我相信他会改的

58

legendlzy

2018-05-11 16:02:16 +08:00

我觉得首先不管多厉害的人都有可能出错
但是我觉得阮一峰的文章更多是浅显的说明问题，可能是为了这个目的特意这么写的
而且这些面试的人不应该有问题才对嘛？只看了代码，不看思路=-=。。。
完全没必要发个文章去 diss。。。

59

Nicksxs

2018-05-11 16:11:10 +08:00

@orangeade 芝士不是奶油？

60

natscat

2018-05-11 16:19:00 +08:00

1

快排这种入门的算法估计都能淘汰不少人了现在混子太多

不是说快排在工作中是否能用上但原理和实现总得知道

61

natscat

2018-05-11 16:21:45 +08:00

@zhicheng #31 那如果面试考算法考啥？我觉得二分查找和快速排序是最基本的了
当然招一个合格的人有多种考察维度但算法这边你不会二分查找和快排我也不指望你能会更复杂的了

62

Pikaping

2018-05-11 16:28:39 +08:00

别提了。。阮一峰日常出错被怼，他发的很多微博低级错误太明显了，只能糊弄对那方面知识完全不懂的人，他的人气是写了这么多年博客积累起来的，但是越来越不靠谱了

63

skadi

2018-05-11 16:32:52 +08:00

@zhicheng 这种是计算机系的教材的基本东西啊...我想你可能有啥误解.

64

davinci

2018-05-11 16:36:22 +08:00

其实阮一峰版本的快排最坏情况的时间复杂度才是 O(n^2)，理想情况即每次划分都是平分，时间复杂度也是 O(nlogn)。空间复杂度最坏情况 O(n^2)，理想情况 O(n)

65

Cbdy

2018-05-11 16:45:10 +08:00

过年的时候用 js 写过一个，不知道写得对不对，和教科书上的类似了
https://github.com/cbdyzj/data-structure/blob/master/sort/quick_sort.ts

66

zhicheng

2018-05-11 16:46:24 +08:00 via iPhone

@skadi 基础的怎么了，错的最多的就是这些，抓细节连 int mid =(low + high) / 2; 都是错的。

@natscat 连应试教育考试也不是考试你 Xxx 定理，而是考如何运用 Xxx 定理。

67

iceheart

2018-05-11 16:48:30 +08:00 via Android

怼了一通，最后跑代码千万量级的一个是 5 秒，一个是 10 秒，差别很大吗？还不是一个级别么？我觉得还是简洁的代码更好看。

68

wheat0r

2018-05-11 16:51:10 +08:00

@Nicksxs 终于能插上话了，芝士还真不是奶油…
芝士对应的是 cheese
奶油是 cream
不管是在国内还是在国外都不是一种东西

69

CastleBUPT

2018-05-11 17:02:08 +08:00

4

@carlclone
“感觉日常本来用到算法的地方就不多，就算是有也是随便写个方法能实现就行了，没去仔细考虑过效率的问题，阮一峰的这个快排目前看来确实不是最优解，至少我还能理解，什么时间空间的完全搞不懂”。
看到这个回复的时候我都要窒息了。
读书无用论真是太有群众基础了。

70

vansouth

2018-05-11 17:04:50 +08:00

1

我只想说，人家阮一峰写的那文章好像是 11 年的，你现在来怼人家····666

71

CFMY

2018-05-11 17:18:27 +08:00

这只是博客又不是教程，现在的人也太不要脸了，为了热度连"完全是错的" 这种标题都取得出来
这作者扪心自问一下，良心不会痛吗

72

zzNucker

2018-05-11 17:23:34 +08:00

毕竟日常怼阮一峰是显示自己牛逼的好途径

73

Biwood

2018-05-11 17:46:56 +08:00

1

在这件事情中发现了两种人：
照本宣科的在面试中直接使用文章的示例代码的人，
以及高兴的上蹿下跳认为自己挖到宝藏了的人。

74

natscat

2018-05-11 17:49:28 +08:00

@zhicheng #66 a^2+b^2=c^定理都背不下来指望在实际生产中运用？

75

grantonzhuang

2018-05-11 17:52:54 +08:00 via Android

看到关于这件事的评论，作为一个前端，感觉自己处在鄙视链的底层……

76

shihira

2018-05-11 17:54:51 +08:00

若是平常人，在博客写了错的排序，评论区大概会有好心人善意指正，一来一往其乐融融
若是阮一峰，嘿，怼！

77

zhicheng

2018-05-11 17:55:46 +08:00

@natscat 记住的应该是 a^2 + b^2 = c^2 而不是 a^2 + b^2 = c^2 的证明过程。就像在实际上，知道快排，知道怎么用及它的特点就可以了，甚至不知道特点也无所谓，因为几乎所有需要排序的地方用的都是快排。

78

shyrock

2018-05-11 17:56:32 +08:00

这篇怼文的数据，怎么说呢，不是很科学。既然指出时间和空间复杂度两方面的错误，怎么就没有测试空间复杂度的数据呢？另外测试数据至少来三个点吧，才看的出来到底两种算法的差距是什么级别的，只有一个点，那 5s 跟 10s 的差距到底意味着什么？

79

shyrock

2018-05-11 17:59:54 +08:00

作为 js 新手，我还有一个小疑问，阮的算法用 splice，效果是移除了原数组的一个数据项，而纠错作者直接用下标获取，没有移除这个数据项。按理说，阮的算法会丢一个数据吧？

80

66beta

2018-05-11 18:02:55 +08:00 via Android

阮老师有 share 精神，怼他的那位，暂时没看出来

81

duan602728596

2018-05-11 18:10:34 +08:00 via iPhone

救救前端的孩子吧，现在前端又是文又是理的，已经变成大杂烩了

82

swulling

2018-05-11 18:12:14 +08:00

1

这个文章里错误也不少。
比如文章作者可以解释下 10000000 元素排列，为什么 O(nlogn)的算法竟然只比被作者钦定为是 O(n^2)的算法快一倍。

合理么？其实阮一峰那个时间复杂度并不是 O(n^2)

83

gggxxxx

2018-05-11 18:18:08 +08:00

我怎么觉得有点孔乙己的风格了呢。
单说多声明几个临时变量这点，就能被判定为是错的？在我看来，既然是写高级编程语言，声明几个变量还有标准不成？
至于效率比拼，这个值得认真讨论。但是不应该来评判面试者。

84

Jakesoft

2018-05-11 18:25:08 +08:00

借楼问一下，排序算法（尤其是快排），开辟两个临时数组真的不可取吗？上次这么写被面试官怼了

85

silhouette

2018-05-11 18:25:51 +08:00 via Android

@zhicheng 对，要扣细节得写成 int mid=(high-low)/2+low; 防一个溢出

86

kangkang

2018-05-11 18:35:13 +08:00

不是很懂，错了就是错了，哪有那么多话讲？

87

wshcdr

2018-05-11 18:35:57 +08:00

阮老师错的地方多了...

88

kangkang

2018-05-11 18:36:34 +08:00

@grantonzhuang 如果你的同行都是评论里那些“信徒”，你应该感到幸运，因为这意味着你只要稍微动动脑子就能超越大多数。。。。

89

bucky

2018-05-11 18:44:51 +08:00

@kangkang 错了本来没什么，可是好多人批评阮一峰套路都是，阮一峰这么低级的错误都犯，真垃圾，看阮一峰是浪费时间，会让你误入歧途，阮一峰是转行的三流程序员，更有甚者还要骂前端的从业者都是垃圾，整个前端都不入流等等

90

bucky

2018-05-11 18:46:07 +08:00

@CastleBUPT 大佬，请问你学了算法后对你的编程能力有哪些实质性的提高？

91

florije

2018-05-11 18:48:43 +08:00

他的博客很不靠谱呀，前面学习 js 的 promise 机制，看了下他的内容，发现根本就不对……
这种热门博客作为小白普及类还是可以，要是当作参考还是算了吧。

92

wysnylc

2018-05-11 18:51:30 +08:00

@orangeade #7 芝士奶油奶酪其实是一个东西,菠萝和凤梨也是一个

93

loveCoding

2018-05-11 18:57:01 +08:00

jdk 还有 bug 呢

94

cuzfinal

2018-05-11 19:03:05 +08:00

阮一峰的代码起码告诉了别人快排里分治的思想

95

DOLLOR

2018-05-11 19:06:06 +08:00 via Android

莫名其妙就上升到整个前端了，不如更上一层楼，黑整个程序员群体岂不美哉

96

roychan

2018-05-11 19:06:59 +08:00

前端为什么要学快排？直接 array.sort() 就可以了。

97

h1367500190

2018-05-11 19:59:14 +08:00

@grantonzhuang 别在意，做好自己的事情就好。我是 PHP+前端，简直是鄙视链最最底端，这种酸味的评论见的多了。“这个世界有两种语言，一种是天天被黑的，一种是没人用的”。评论里很多人估计连 HTML5 的自关闭标签都写错，却到处对前端抛出论点却没有论据，守着自己的一亩三分地。

哪天前端不被喷了才是最需要担心的。毕竟现在是个程序员还能用 jQuery 写个页面，过个 5-10 年，就能把一批“大神”刷掉

98

h1367500190

2018-05-11 20:03:36 +08:00

@shyrock 你看他最后一行：
return quickSort(left).concat([pivot], quickSort(right));

99

CastleBUPT

2018-05-11 20:07:56 +08:00

@bucky
作为菜鸡，我觉得解算法题对搬砖的来说，
一个是能把握自己写的代码的时间和空间复杂度，不至于太离谱，会弄个 O(n3)出来；
另一个是锻炼自己解小问题的能力；
还有就是算法的套路和工程的套路差不多，会的套路越多，看工程代码和写工程代码就越快。

100

livc

2018-05-11 20:22:18 +08:00

1

ryf 好像对待别人的纠错从来没改吧？

1 2

❮

❯