Toptal连接了前3%的 自由开发人员 世界各地.
快速排序方式
动画，代码，分析，并讨论了快速排序(3路分区)在4个初始条件.
button.
算法
_#选择透视_
交换一个(n,兰德(1,n))
3-way分区
I = 1 k = 1 p = n
while i < p,
if a[i] 讨论
与标准的2路分区版本相比，快速排序的3路分区变体的开销略高. 两者都有相同的优点, 典型的, 最坏的情况是时间限制, 但是这个版本在使用少数唯一键排序的非常常见的情况下是高度自适应的.
The 3-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, 并且执行了比必要时更多的交换. 文中给出了一种更有效、更精细的三向划分方法 快速排序是最优的 罗伯特·塞奇威克和乔恩·本特利著.
当不需要稳定性时，快速排序是首选的通用排序算法. 最近, 提出了一种新的双支点三向划分方法，在理论和实践上都优于单支点三向划分方法.
关键
- 黑色值排序.
- 灰度值未排序.
- 深灰色值表示当前间隔.
- 一对红色三角形标记k和p(见代码).
属性
- 不稳定
- O(lg(n))的额外空间
- O(n2)时间，但通常是O(n·lg(n))时间
- 自适应:当0(1)个唯一键时O(n)时间