《阮一峰版快速排序完全是错的》一文是否存在事实错误？ 第1页

讲技术的部分：

1. 之前我一直误认为自己写的原地快排的空间复杂度是O(1)，但是通过这次网友的提醒（该网友已在评论区出现 @原建业 ），我发现居然是O(log(n))，因为递归不是尾递归必须用栈，思考了下，好像并没有办法优化，怎么写都要O(log(n))。
2. 非原地快排，就算敞开了铺着写，假设我们每层递归都产生临时数组，那么空间占用应该是 n + n/2 + n/4 + n/8 + …… ≈ 2n，也就是说，空间复杂度是O(n)
3. 众所周知，快排进行了log(n)次O(n)的partition，所以时间复杂度是O(nlog(n))，阮老师犯下了“弥天大罪”在每次partition之前选取中间值的时候进行了一次splice，而splice的时间复杂度是O(n)，partition的时间复杂度也是O(n)，请问O(n) + O(n)是？

结论：阮老师写的是非原地快排，空间复杂度从O(log(n))上升到了O(n)，而每次使用splice从无序的数组中间位置选取中值是毫无意义的浪费，但并没有改变时间复杂度，他写的快排时间复杂度仍然是O(nlog(n))。从实际测试结果来看，阮老师的代码性能也确实不高。

PS.阮老师这篇作于2011年，那时候阮老师的职业是什么，大家不妨了解下。

讲人的部分：

这位ideawu其人，张口闭口前端如何，透露出一股优越感，令人生厌：

“大多数前端只会表面皮毛”