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

[cairnechen]

起因是 ideawu 发微博吐槽几乎所有的前端面试者的快排实现都是阮一峰的错误版本。

v 友们怎么看这个问题？

完整分析见 https://juejin.im/post/5af4902a6fb9a07abf728c40

[tschenhui]

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

[ryd994]

@zhicheng 可现在某些人就是这个论点
阮一峰 vs 正规算法教材

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

简化版看看娱乐一下还是可以的。想学到干货还是算了。

[ryd994]

mmm
何其相似

[bucky]

@zhicheng 你先别急着尴尬，如果别人讲的清楚，即使有错误，你也能发现， 而讲不明白的，你连发现错误的机会都没必要，老师的作用从来都不是字典，不是标准答案，否则直接交给机器人不就行了，要什么老师？在学习的路上，有错误从来不是什么大不了的事情，发现不了错误才是

[quintic]

我觉得作者可能没弄清楚*渐进*复杂度的意思：只测一个点的速度没有任何意义，要看 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 )

因此，阮一峰的实现达到了快排的渐进时间复杂度，没有问题。（其实我个人偏好这种损失一定常数，但保证简洁正确的写法）

[zhicheng]

@ryd994 从你们喷的点上，我并不认为阮一峰的算法是错的，你可以说有更好的写法。但用 JavaScript 实现快排本身就很娱乐了，本身也是一个演示级的东西。

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

用一个文绉绉成语表示一下就是，你们有点儿吹毛求疵了。

[20015jjw]

@zhicheng 话不多说 参考#143

不知道你们这东西有什么好洗的 错的就是错的啊 居然还能强行 defend 说这个答案宗旨上是对的...？还表达清晰...？面试我要看到这种直接拒好吧... 这算法名字就叫 quicksort 写出 n^2 还有理？ prod 里会写 quicksort 可能没那么重要，但是对于语言自带操作的理解是很重要的，不然小小一行在大厂可能就是六位甚至七位的电费...

[zhicheng]

@20015jjw you are right.

[quintic]

@20015jjw 不是，朋友，阮写的是对的，复杂度是 n log n 不是 n 方，是你搞错了。

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

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

很奇怪怎么会吵了一百多楼还没搞清楚……

[YenvY]

你们是觉得大 V 级的 blogger 有必要为自己的文章的后果考虑，有错就改，最好还能把评论区只会喊 666 的人挨个艾特一遍，否则不是人血馒头也是误人子弟，像阮这样的大概会被评个“前端教育界模范和罪人”？
还是说只要写博客就相当于承诺了上述那些东西；
还是说这些狗屎都是闲的蛋疼的人才去提起，老子承认错误，想改就改，我又没说我的播客要教你什么东西，我凭什么要负这样那样的责任
说到这里我就想请教诸位了，有没有相关的可以引用的文档可以显示的说明自己的博客 /Repo/Project 一不保证正确二不保证改正，欢迎 PR/评论 /参与维护，也欢迎给我打钱买咖啡，但只是当作对以往工作的肯定，我还是坚持前两点。这种为了懒和不用负责任的东西总会有人提前想到的吧
反正围绕阮老师的论战一年有好几轮，我觉得可以存在这样的一份文档，如果有共识就趁早文档化，省的总拿这些事儿抬杠，还没人用淋语，特别没观赏性

[nikolai]

还不是因为背题就可以过面试，成本低收益高，大家就去背了

[tsui]

原文作者本科基础也不行啊，刚开始 O(1)复杂度那个例子，他不知道什么是 loop unrolling 么

[vindurriel]

@davinci 你说的对 左耳朵耗子的评论错了 平均时间复杂度不是 n2

[zhaoweichen]

@EmbraceZ
@wizardoz 说的没问题，尾递归优化有条件 (比如，能转换成用循环的实现)。

[zhaoweichen]

想了半天也没想明白阮老师的写法怎么就 O(n^2)了...
@davinci @vindurriel 要不是看你们评论，我还以为我算法白学了 :)

[zhaoweichen]

@tsui “完整分析”里面，O(1)那个例子不是循环啊。
问题应该是对输入规模的理解问题。第二次的输入也没超 64bit...

话说，我没接触 javascript 的类型系统，javascript 是像 python 那样无限精度的么？还是说弱类型系统可以根据输入推测类型？

[zhaoweichen]

@quintic 平均时间复杂度的确没问题，但是空间复杂度差了很多。
如果很多这样的程序在浏览器里跑，就算时间复杂度没问题，系统性能也会受影响嘛~

[binux]

@BXIA #103 你这明明是 O(n) 的

[markx]

我感觉，splice 是为了遍历时排除掉 pivot， 开新数组来递归也没问题啊。 这样的写法虽然空间上效率不好，但是确实更容易看懂，作为教程是很好的。 而且，我也不觉得这个实现是错误的。我认为快排的关键是 pivot 和 partition，这个这两点这个实现并没有搞错。

错的可能是，大家把教程代码当做工程代码了。

[tsui]

@zhaoweichen 中午粗看了一眼以为它用循环次数来说明什么
重看了一眼不明白它这函数到底干啥了
function increase(n) {
n++;
}
连个 return 都没有而且 javascript pass by value 啊