1. 基本原理
快速排序由 Tony Hoare 发表于 1961 年。是一种分治算法,基本步骤:
特别注意:不同的 pivot 选择策略、不同的分区策略,都会对快排性能产生影响。
时间复杂度
最坏:O(n^2) 、平均:O(nlogn)
下面介绍快速排序的几种不同实现
2. 实现1:Lomuto 分区策略
Nico Lomuto 分区策略,出自《算法导论》,虽然效率不算高,但容易理解。
图:Lomuto 分区策略
3. 实现2:Lomuto 变形
跟Lomuto差不多
动画
代码示例
4. 实现3:Hoare 分区策略
Hoare 分区规则是快速排序作者最原始的规则,它比Lomuto分区规则更高效。而且也不是简单的选择开头或结尾元素作为 pivot,最大限度避免算法退化到 O(n^2)。
图:Hoare 分区策略
5. 实现4:DNF(荷兰旗)分区策略
假设数组中所有元素都相同(极端场景):
DNF(Dutch national flag,荷兰旗)算法就是这类问题一种解,将数组分3个区,“<pivot”区、“=pivot区”、“>pivot区”。由于“=pivot区”实际已经有序,所以只有“<pivot区”和“>pivot区”参与递归排序即可。
Dutch national flag(DNF) 算法
叕是 Edsger Dijkstra
这货提出来的
某盒子中有n个球,每个球的颜色可以是红、蓝、白,现在要求把球按照红、蓝、白的顺序摆放。这个问题叫做荷兰旗问题(荷兰旗由红、蓝、白三色组成)
图:DNF 分区策略
5. 实现4:DualPivotQuickSort
JDK7 对【基本数据类型】数组的
默认排序算法是
DualPivotQuickSort
是快速排序的超豪华版本
The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
图:JDK,Arrays源码节选