快速排序 空间复杂度_一篇文章让你真正了解快速排序

(给算法爱好者加星标，修炼编程内功)

来源：汤姆C

https://segmentfault.com/a/1190000017314698

只要是个工程师，就或多或少的知道快排，其中很多人都能轻松的写出一个快排的实现。但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践？本文从一个争执讲起，通过生动详实的例子让你真正了解快排。嗯，这确实是一篇炒冷饭的文章，但我希望能把冷饭炒成好吃的蛋炒饭。闲话少叙，马上开始~

1. 阮一峰快排事件

整个事件用一句话来概括，就是有人diss阮一峰的快排写的不对，如下图。其实从图上也看到了，这个微博并没有发酵起来，直到一篇发表在掘金上的文章《阮一峰版快速排序完全是错的》(文章已经不能访问)，然后又被人提问到知乎上，整个事情才变得热闹了起来。Diss的主要点在于两个：

• 一个是拿哨兵用的splice而不是数组下标

• 一个是算法使用的是额外空间而不是原地分割

哨兵：快排中的被选中作为比较对象的基准元素

这件事情上，绝大多数同学都支持阮老师。其实，我觉得这