Lei Mao's Log Book
·
分区算法
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
分区算法是一种高效且实用的O(N)算法，用于排序和选择。本文介绍了自定义双指针方法和C++标准库函数std::partition的实现。两种实现的主要区别在于交换次数。
🎯
关键要点
- 分区算法是一种高效且实用的O(N)算法，常用于排序和选择。
- 分区算法是快速排序和线性时间选择算法的基础。
- 自定义双指针方法用于实现分区算法。
- C++标准库提供了std::partition函数，可以替代自定义的分区函数。
- 自定义方法和标准库函数的主要区别在于交换次数，标准库函数最多有N次交换，而自定义方法最多有N/2次交换。
➡️
