Partition Algorithm

draft three-way

算法的核心是：

1. 选择一个元素为 pivot，并进行 partition：
2. 把剩下的元素中小于该元素的放在左边，大于该元素的放在右边
3. 且该 pivot 最终处于正确的位置上
4. 选择哪个元素为 pivot。最基础的是选择第一个，但对已排序的数组时间会变成 \(O(n^2)\)。一般采用：
5. 随机选择
6. 中位数
7. 其它更高级选择方式

Partition 有两种方法，比较好写的 Lomuto 和发明快速排序的 Hoare 的算法。

1. Partition 中的 Lomuto 算法
2. Hoare’s Partition Algorithm

代码详见：algo/sorting.py at main · shao-wang-me/algo (github.com)

flashcards

Partition 的复杂度:: \(O(n)\)，因为要遍历所有元素，无论是快慢指针还是首尾指针

Partition 的应用
?

1. 快速排序，\(O(n)\)
2. 快速选择，即寻找第 k 大的元素（故包含寻找中位数），\(O(n)\)