分区算法

分区算法的实现 更多...

分区算法 的协作图:

函数
template<typename Iterator, typename Predicate>
constexpr Iterator	partition (Iterator first, Iterator last, Predicate pred)
	分区算法
template<typename Iterator, typename Compare>
constexpr Iterator	lomuto_partition (Iterator first, Iterator last, Compare comp)
	Lomuto 分区算法（基准值归位）
template<typename Iterator>
constexpr Iterator	lomuto_partition (Iterator first, Iterator last)
	Lomuto 分区算法（基准值归位）

详细描述

分区算法的实现

函数说明

lomuto_partition() [1/2]

template<typename Iterator>

Iterator lomuto_partition ( Iterator first, Iterator last )

constexpr

Lomuto 分区算法（基准值归位）

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

返回

基准值最终的迭代器位置

在文件 partition.hpp 第 155 行定义.

引用了 lomuto_partition().

lomuto_partition() [2/2]

template<typename Iterator, typename Compare>

Iterator lomuto_partition ( Iterator first, Iterator last, Compare comp )

constexpr

Lomuto 分区算法（基准值归位）

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

基准值最终的迭代器位置

选择 first、mid、last-1 的中位数作为基准值，将其交换到 first， 使用 Lomuto 方案分区，最后将基准值放置到正确位置并返回。

在文件 partition.hpp 第 119 行定义.

引用了 is_ranges_rnd_iter_v , 以及 iter_swap().

被这些函数引用 introspective_sort(), lomuto_partition(), nth_element() , 以及 quick_sort().

partition()

template<typename Iterator, typename Predicate>

Iterator partition ( Iterator first, Iterator last, Predicate pred )

constexpr

分区算法

模板参数

Iterator	迭代器类型
Predicate	谓词类型

参数

first	范围起始
last	范围结束
pred	一元谓词

返回

指向第二部分第一个元素的迭代器

将范围 [first, last) 重新排列，使得所有满足谓词 pred 的元素都出现在不满足谓词的元素之前。 不保证相同类别的元素保持原始相对顺序。

算法使用双向迭代器，从两端向中间扫描：

1. 从前向后找到第一个不满足谓词的元素
2. 从后向前找到第一个满足谓词的元素
3. 交换这两个元素
4. 重复直到两个扫描指针相遇

在文件 partition.hpp 第 46 行定义.

引用了 is_invocable_v, is_ranges_bid_iter_v , 以及 iter_swap().